题目描述
给出一个长度不超过 200 的由小写英文字母组成的字母串（该字串以每行 20 个字母的方式输入，且保证每行一定为 20 个）。要求将此字母串分成 k 份，且每份中包含的单词个数加起来总数最大。
每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不能包含 th。
单词在给出的一个不超过 6 个单词的字典中。
要求输出最大的个数。
输入格式
每组的第一行有两个正整数 p,k。 p 表示字串的行数，k 表示分为 k 个部分。
接下来的 p 行，每行均有 20 个字符。
再接下来有一个正整数 s，表示字典中单词个数。 接下来的 s 行，每行均有一个单词。
输出格式
1个整数，分别对应每组测试数据的相应结果。
思路：dp。我们用dp[i][j]表示字符串i位置分成j块所包含的单词数量，那么，状态转移方程为:dp[i][j] = dp[u][j-1]+sum[u+1][i]。其中u为小于i的断点，sum[i][j]表示i位置到j位置包含的单词数量。我们可以先预处理出来。根据题意，在处理sum的时候我们可以倒序处理。
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int p = sc.nextInt();
int k = sc.nextInt();
String str = "";
for(int i=0;i<p;i++){
String t = sc.next();
str += t;
}
int len = str.length();
int s = sc.nextInt();
String[] arr = new String[s+5];
for(int i=0;i<s;i++) arr[i] = sc.next();
int[][]dp = new int[300][50];//dp[i][j]表示i位置分成j块所包含的最大单词数量 dp[i][j] = dp[u][j-1] + sum[u+1][i]
int[][] sum = new int[300][300]; //sum[i][j]表示i到j包含的单词数量
for(int i=len-1;i>=0;i--){
for(int j=i;j>=0;j--){
sum[j][i] = sum[j+1][i];
String temp = str.substring(j,i+1);
for(int q=0;q<s;q++){
if(temp.indexOf(arr[q])==0){
sum[j][i]++;
break;
}
}
}
}
for(int i=0;i<len;i++){
dp[i][1] = sum[0][i];
for(int u=0;u<i;u++)
for(int j=2;j<=k&&j<=u+1;j++){
dp[i][j] = Math.max(dp[i][j],dp[u][j-1]+sum[u+1][i]);
}
}
System.out.println(dp[len-1][k]);
}
}