2349 - 统计单词个数
时间限制 : 1 秒
内存限制 : 125 MB
给出一个长度不超过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行，每行输入一个单词。
<br />
题目输出
对于每组输入数据，输出一个整数，分别对应每组测试数据的相应结果。
下面是对样例数据的说明：
样例数据中对字母串分割的方式是：this/isabookyoua/reaoh
输入/输出样例
输入格式
1 3 thisisabookyouareaoh 4 is a ok sab
输出格式
7
C++解答
#include<cstdio> #include<cstring> int word[201][201],dp[201][201][41]; char c[21],w[6][10],c0[201],c1[201]; int d,p,k,s,Max,le[6],len; int main(){ int i,j,l,m,yes,x,st; scanf("%d%d",&p,&k); for(j=0;j<p;j++){ scanf("%s",c); if(!j)strcpy(c0, c); else strcat(c0, c); } len=strlen(c0); scanf("%d",&s); for(j=0;j<s;j++){ scanf("%s",w[j]); le[j]=strlen(w[j]); } for(i=0;i<len;i++)for(j=0;j<len;j++)word[i][j]=0; for(i=len-1;i>=0;i--)for(j=len-1;j>=0;j--){ for(l=0;l<s;l++){ yes=0; if(c0[j]==w[l][0]&&le[l]<=i-j+1){ yes=1; for(m=0;m<le[l];m++) if(c0[j+m]!= w[l][m]){yes=0;break;} } if(yes==1)break; } if(yes==1)word[j][i]=word[j+1][i]+1; else word[j][i]=word[j+1][i]; } for(st=1;st<=k;st++)for(i=0;i<len-st+1;i++)for(j = i+st-1; j < len; j++){ if(st==1){ dp[i][j][st]=word[i][j]; continue; } for(Max=0,l=i+st-2;l<j;l++){ x=dp[i][l][st-1]+word[l+1][j]; if(x>Max)Max=x; } dp[i][j][st]=Max; } printf("%d\n",dp[0][len-1][k]); return 0; }