Codevs 1040 统计单词个数

1040 统计单词个数

2001年NOIP全国联赛提高组

时间限制: 1 s　　　　空间限制: 128000 KB　　　　题目等级 : 黄金 Gold

题目描述 Description

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)（管理员注：这里的不能再用指的是位置，不是字母本身。比如thisis可以算做包含2个is）。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。

输入描述 Input Description

第一行为一个正整数(0<n<=5)表示有n组测试数据
每组的第一行有二个正整数(p，k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)
接下来的s行，每行均有一个单词。

输出描述 Output Description

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

样例输入 Sample Input

1
1 3
thisisabookyouareaoh
4
is
a
ok
sab

样例输出 Sample Output

数据范围及提示 Data Size & Hint

this/isabookyoua/reaoh

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 int T,p,k,sum,g[401],f[201][201],ans[201][41];
 6 string s,ss,word[7];
 7 int len_tot,len[7];
 8 void pre()
 9 {
10     s.clear();
11     for(int i=1;i<=6;i++)
12     word[i].clear();
13     memset(g,0,sizeof(g));
14     memset(f,0,sizeof(f));
15     memset(ans,0,sizeof(ans));
16 }
17 int main()
18 {
19     scanf("%d",&T);
20     while(T--){
21         pre();
22         scanf("%d%d",&p,&k);
23         while(p--){
24             cin>>ss;
25             s+=ss;
26         }
27         len_tot=s.length();
28         scanf("%d",&sum);
29         for(int i=1;i<=sum;i++) cin>>word[i];
30         for(int i=1;i<=sum;i++) len[i]=word[i].length();
31         memset(g,127,sizeof(g));
32         for(int i=0;i<len_tot;i++)
33          for(int j=1;j<=sum;j++)
34           if(s.substr(i,len[j])==word[j]&&g[i]>len[j]) g[i]=len[j];
35         //substr // 获得字符串从第i位开始长度为len[j]的字符串
36         for(int i=0;i<len_tot;i++)
37          for(int j=i;j<len_tot;j++)
38           for(int l=i;l<=j;l++){
39             if(g[l]>400) continue;
40             if(l+g[l]-1<=j) f[i][j]++;
41           }    
42         for(int i=0;i<len_tot;i++)
43             ans[i][1]=f[0][i];
44         for(int i=2;i<=k;i++)
45           for(int j=i;j<len_tot;j++)
46             for(int l=i-1;l<j;l++)
47               ans[j][i]=max(ans[j][i],ans[l][i-1]+f[l+1][j]);
48         printf("%d
",ans[len_tot-1][k]);
49     } 
50 }