题目描述
给出一个长度不超过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
比较简单的DP
每个字母只可能构成一个单词来贡献答案，暴力处理d[i]为从i开始构成单词的最近位置，O(n*n*6)
f[i][j]表示前i个字符分成j组
f[i][j]=max{f[k][j-1]+w|j<=k<=i}
k逆序枚举，w可以顺便递推出来 PS：一开始煞笔的把退出循环写错位置了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=,M=;
char s[N],word[][N],len[];
int p,m,n,num;
int d[N],f[N][M];
void dp(){
n=strlen(s+);
memset(d,,sizeof(d));
for(int i=;i<=n;i++){
for(int j=;j<=num;j++){
if(n-i+<len[j]||d[i]<=len[j]) continue;
int flag=;
for(int k=;k<len[j];k++)
if(s[i+k]!=word[j][k+]) {flag=;break;}
if(flag) continue;
d[i]=i+len[j]-;//printf("wo %d\n",j);
}
//printf("d %d %d\n",i,d[i]);
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
int w=;
for(int k=i;k>=j;k--){
if(d[k]<=i) w++;
f[i][j]=max(f[i][j],f[k-][j-]+w);//w=(j,i)
}
} }
int main(){
scanf("%d%d",&p,&m);
for(int i=;i<=p;i++) scanf("%s",s++*(i-));
scanf("%d",&num);
for(int i=;i<=num;i++) scanf("%s",word[i]+),len[i]=strlen(word[i]+);//,printf("word %d %d\n",i,len[i]);
dp();
printf("%d",f[n][m]);
}