统计单词个数
题目描述
给出一个长度不超过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，及其转移方程：
f[i][k]=Max{f[j][k-1],s[j+1][i]}（i为位置，k为次数，s为区间单词数）
注意到一个单词被用过后首字母不能再用，所以如果（j，i）区间以j为首存在单词，则：s[j][i]=s[j+1][i]+1 否则s[j][i]=s[j+1][i]
注意边界，f[i][k]（i<k不存在，不能由其转移，否则gg，惨痛的教训...）
代码：
//2017.11.7
//DP
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int Max(int x,int y){return x>y?x:y;}
namespace lys{
],c[][];
][],dp[][];
int p,K,n;
bool exist(int x,int y){
;
int i,j,k;
;i<n;i++){
if(strlen(c[i])>l) continue ;
k=x;
;j<strlen(c[i]);j++) if(c[i][j]!=s[k++]) break ;
if(j==strlen(c[i])) return true ;
}
return false ;
}
int main(){
int i,j,k;
scanf("%d%d",&p,&K);
;i<p;i++) scanf();
scanf("%d",&n);
;i<n;i++) scanf("%s",c[i]);
-;i>=;i--)
;j--){
][i]+;
][i];
}
;i<p*;i++) dp[i][]=num[][i];
;i<p*;i++)
;k<=K;k++)
;j<i;j++) dp[i][k]=Max(dp[i][k],dp[j][k-]+num[j+][i]);
printf(*p-][K]);
;
}
}
int main(){
lys::main();
;
}