题目描述
给出一个长度不超过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：
1 3
thisisabookyouareaoh
4
is
a
ok
sab
输出样例#1：
7
说明
this/isabookyoua/reaoh
两次DP，第一次预处理出区间[i][j]内的单词个数，第二次处理分段最优解。
/*By SilverN*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
int p,K;
int len;
int n;
char s[];
char a[][];
bool fd(int st,int ed){
for(int i=;i<=n;i++){
char *p=strstr(s+st,a[i]+);
if(p==NULL)continue;
if(p-&s[st]== && strlen(a[i]+)<=ed-st+)
return ;
}
return ;
}
int f[][];
int cnt[][];
int dp(){
int i,j,k;
for(i=;i<=K;i++)f[i][i]=f[i-][i-]+cnt[i][i];
for(i=;i<=len;i++)f[i][]=cnt[][i];
for(i=;i<=len;i++)
for(j=;j<i && j<=K;j++)
for(k=j;k<i;k++){
f[i][j]=max(f[i][j],f[k][j-]+cnt[k+][i]);
}
return f[len][K];
}
int main(){
scanf("%d%d",&p,&K);
int i,j;
char tmp[];
for(i=;i<=p;++i){
scanf("%s",tmp);
strcat(s+,tmp);
}
len=*p;
scanf("%d",&n);
for(i=;i<=n;i++){scanf("%s",a[i]+);}
for(i=len;i;--i){
for(j=i;j;--j){
if(fd(j,i)) cnt[j][i]=cnt[j+][i]+;
else cnt[j][i]=cnt[j+][i];
}
}
cout<<dp()<<endl;
return ;
}