题目描述

给出一个长度不超过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行，每行均有一个单词。

一个整数，分别对应每组测试数据的相应结果。

输入输出样例

1 3thisisabookyouareaoh4isaoksab

7

说明

this/isabookyoua/reaoh

 1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #define LL long long 8 using namespace std; 9 int p,K;10 int len;11 int n;12 char s[240];13 char a[240][240];14 bool fd(int st,int ed){15     for(int i=1;i<=n;i++){16         char *p=strstr(s+st,a[i]+1);17         if(p==NULL)continue;18         if(p-&s[st]==0 && strlen(a[i]+1)<=ed-st+1)19             return 1;20     }21     return 0;22 }23 int f[240][240];24 int cnt[240][240];25 int dp(){26     int i,j,k;27     for(i=1;i<=K;i++)f[i][i]=f[i-1][i-1]+cnt[i][i];28     for(i=1;i<=len;i++)f[i][1]=cnt[1][i];29     for(i=1;i<=len;i++)30      for(j=1;j<i && j<=K;j++)31       for(k=j;k<i;k++){32           f[i][j]=max(f[i][j],f[k][j-1]+cnt[k+1][i]);33       }34     return f[len][K];35 }36 int main(){37     scanf("%d%d",&p,&K);38     int i,j;39     char tmp[24];40     for(i=1;i<=p;++i){41         scanf("%s",tmp);42         strcat(s+1,tmp);43     }44     len=20*p;45     scanf("%d",&n);46     for(i=1;i<=n;i++){scanf("%s",a[i]+1);}47     for(i=len;i;--i){48         for(j=i;j;--j){49             if(fd(j,i))    cnt[j][i]=cnt[j+1][i]+1;50             else cnt[j][i]=cnt[j+1][i];51         }52     }53     cout<<dp()<<endl;54     return 0;55 }