codevs 1040 统计单词个数

2001年NOIP全国联赛提高组

 题目等级 : 黄金 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

7

目标：前i个字符中划分为j个部分包含的单词数

如果知道i——j包含的单词数，动态规划可推出答案。

若想知道i——j包含的单词数，处理出以每个位置为起点是否有单词、单词长度可推出。

所以：

ans[j][i]表示前j个字符划分为i个部分包含的单词数

预处理：f[i][j] i——j包含的单词数   g[i]=j 以i为起点有长为j的单词

f数组处理：如果i+g[i]-1<=j,那么f[i][j]里包含以i为起点长为j的单词

状态转移：ans[j][i]=max(ans[k][i-1]+f[k+1][j])

#include
          
           #include
           
            #include
            
             using namespace std;int T,p,k,sum,g[401],f[201][201],ans[201][41];string s,ss,word[7];int len_tot,len[7];void pre(){    s.clear();    for(int i=1;i<=6;i++)    word[i].clear();    memset(g,0,sizeof(g));    memset(f,0,sizeof(f));    memset(ans,0,sizeof(ans));}int main(){    scanf("%d",&T);    while(T--)    {        pre();        scanf("%d%d",&p,&k);        while(p--)        {            cin>>ss;            s+=ss;        }        len_tot=s.length();        scanf("%d",&sum);        for(int i=1;i<=sum;i++) cin>>word[i];        for(int i=1;i<=sum;i++) len[i]=word[i].length();        memset(g,127,sizeof(g));        for(int i=0;i
             
              len[j]) g[i]=len[j];        for(int i=0;i
              
               400) continue;             if(l+g[l]-1<=j) f[i][j]++;         }            for(int i=0;i