题目描述 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
数据范围及提示 Data Size & Hint
this/isabookyoua/reaoh
有一点坑的dp
#include<cstdio>
#include<cstring>
#define LL long long
char ch[210],a[10][210];
LL f[210][10];
int l[10],mn[210];
int p,m,k;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
bool mrk(int k,int x)
{
if(l[k]+x-1>p*20)return 0;
for(int i=1;i<=l[k];i++)
if(a[k][i]!=ch[x+i-1])return 0;
return 1;
}
int calc(int x,int y)
{
int sum=0;
for(int i=x;i<=y;i++)
if(mn[i]<=y)sum++;
return sum;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(mn,127/3,sizeof(mn));
memset(ch,0,sizeof(ch));
memset(f,-1,sizeof(f));
scanf("%d%d",&p,&m);
for (int i=1;i<=p;i++)
for (int j=1;j<=20;j++)
{
char c=getchar();
while (c<'a'||c>'z')c=getchar();
ch[20*(i-1)+j]=c;
}
scanf("%d",&k);
for(int i=1;i<=k;i++)
scanf("%s",a[i]+1);
for (int i=1;i<=k;i++)
l[i]=strlen(a[i]+1);
for (int i=1;i<=p*20;i++)
for (int j=1;j<=k;j++)
if (mrk(j,i))mn[i]=min(mn[i],i+l[j]-1);
f[0][0]=0;
for(int i=1;i<=p*20;i++)
for(int j=0;j<i;j++)
{
int t=calc(j+1,i);
for(int l=1;l<=m;l++)
if(f[j][l-1]!=-1)
f[i][l]=max(f[i][l],f[j][l-1]+t);
}
printf("%d\n",f[p*20][m]);
}
return 0;
}