题目描述
给出一个长度不超过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行，每行均有一个单词。
输出格式：
一个整数，分别对应每组测试数据的相应结果。
输入输出样例
说明
this/isabookyoua/reaoh
Solution
这道题,正解是DP。
我们需要先对其进行预处理.即先预处理出每个单词的起始位置.
状态:
f[i][j] 代表到第 i 个字母分成 j 块的最大值
状态转移:
一开始一直冥思苦想 要讨论好多种结果 没想出来...
然后 最后发现直接倒序枚举 最后一块 的起点即可 同时统计当前最后一块有多少个单词.
即 :
f [ i ][ j ] = max ( f[ i - 1 ][ j - 1 ] + t , f[ i ][ j ]);
t 即为最后分的一块里含有的单词.
代码
#include<bits/stdc++.h> using namespace std; char text[205],word[10][205]; int num,p,k; int v[205],t[205][10]; int f[205][205],kk; int main() { char ch[30]; cin>>p>>k; for(int i=1;i<=p;i++) { scanf("%s",ch); for(int j=0;j<20;j++) {text[num]=ch[j];num++;} } int len=strlen(text); cin>>kk; for(int i=1;i<=kk;i++) scanf("%s",word[i]); for(int i=1;i<=kk;i++) for(int j=0;j<len;j++) { int pd=1; if(text[j]==word[i][0]) { for(int k=1;k<strlen(word[i]);k++) {if(text[j+k]!=word[i][k]){pd=0;break;}} if(pd==1) v[j]=j+strlen(word[i])-1; } } for(int i=0;i<len;i++) for(int j=1;j<=k;j++) { int t=0; if(j==1) { for(int kk=i;kk>=j-1;kk--) if(v[kk]!=0&&v[kk]<=i)t++; f[i][j]=t; } else for(int kk=i;kk>=j-1;kk--) { if(v[kk]!=0&&v[kk]<=i)t++; f[i][j]=max(f[kk-1][j-1]+t,f[i][j]); } } cout<<f[len-1][k]<<endl; }