题目描述
给出一个长度不超过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，看了好久好久才明白过来
讲一下我的思路（和人家学来的）
输入时就把好几行字符串处理成大长串，方便以后的使用。
d[i]表示以s[i]为首字母如果存在单词的情况下最短的单词末尾坐标（苦心看了好久好久）
dp[i][j]是指前i个字符分成j组的最优解
ans存储在dp[n][m]中
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int p,n,m,dp[1000][1000],dis[2050],num; char word[10][100]; char s[2050]; int len[10]; void DP(){ memset(dis,127,sizeof(dis)); for(int i=1;i<=n;i++){//枚举大长串中的每个位置 for(int j=1;j<=num;j++){//枚举每个单词 if((dis[i]<=(i+len[j]-1))||(i+len[j]-1>n))continue; //还有可能纳入的长度比这个单词的长度还短 //现有的dis值比即将讨论的dis值更优，这两种情况出现一种可以直接忽略这个单词 bool flag=0; for(int k=0;k<len[j];k++){//枚举单词中每个字母，比对 if(s[i+k]!=word[j][k+1]){flag=1;break;}//如果有差错，说明不存在这个单词，看下一个 } if(flag==1)continue; dis[i]=min(dis[i],i+len[j]-1);//如果是这个单词，纳入单词长度 } } for(int i=1;i<=n;i++){//长度为i的串 for(int j=1;j<=m;j++){//分成m部分 int w=0; for(int k=i;k>=j;k--){//阶段讨论 if(dis[k]<=i)w++; dp[i][j]=max(dp[i][j],dp[k-1][j-1]+w); } } } } int main(){ scanf("%d%d",&p,&m); for(int i=1;i<=p;i++)scanf("%s",s+1+20*(i-1)); n=strlen(s+1);//大长串总长 scanf("%d",&num); for(int i=1;i<=num;i++)scanf("%s",word[i]+1),len[i]=strlen(word[i]+1); DP(); printf("%d ",dp[n][m]); return 0; }