描述
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
格式
输入格式
第一行有二个正整数(p，k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)
接下来的s行，每行均有一个单词。
输出格式
输出一个整数，即最大的个数
限制
每个测试点1s
来源
NOIP2001第三题
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 #include<cstring> 7 using namespace std; 8 char T[50000],ss[50000];//T是目标串 9 char P[10][1000];//P是模式串 10 int sum[1000][1000];//sum[i][j]表示T串中 i 到 j 之间单词个数 11 int f[1000][1000];//f[i][j]表示吧前 i个字符分成 j部分的最优值 12 int n,k,m,tot; 13 bool jud(int l,int r,int num){ 14 if(strlen(P[num]+1)>r-l+1){//要匹配长度比整个串还长 15 return false; 16 } 17 int now=1; 18 for(;;){ 19 if(T[l]!=P[num][now]) 20 return false; 21 else if(now==strlen(P[num]+1)) 22 return true; 23 l++,now++; 24 } 25 } 26 int main(){ 27 28 scanf("%d%d",&n,&k); 29 tot=20*n; 30 31 for(int i=1;i<=n;i++){ 32 scanf("%s",ss+1); 33 for(int j=1;j<=20;j++){ 34 int now=20*(i-1)+j; 35 T[now]=ss[j]; 36 } 37 } 38 39 scanf("%d",&m); 40 for(int i=1;i<=m;i++){ 41 scanf("%s",P[i]+1); 42 } 43 for(int i=tot;i>=1;i--){//末 44 for(int j=i;j>=1;j--){//始 45 for(int v=1;v<=m;v++){//从 i到 j 有字符串P[v] 46 if(jud(j,i,v)==true){ 47 sum[j][i]=sum[j+1][i]+1; 48 break; 49 } 50 sum[j][i]=sum[j+1][i]; 51 } 52 } 53 } 54 55 for(int i=1;i<=tot;i++) f[i][1]=sum[1][i]; 56 if(k==0){ 57 cout<<sum[1][tot]; 58 return 0; 59 } 60 61 for(int i=1;i<=tot;i++){//前i个字母 62 for(int j=1;j<=k&&j<=i;j++){//用j次划分,划分份数不会超过 k 和 i 63 for(int t=k;t<i;t++){//在t处断一次 64 f[i][j]=max(f[i][j],f[t][j-1]+sum[t+1][i]); 65 } 66 } 67 } 68 cout<<f[tot][k]<<endl; 69 return 0; 70 }