题目描述
给出一个长度不超过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
不得不说最开始我连题意都没看懂，2333。
大概意思是说，给你一串字符，你将这个字符划分成k块，使每一块包含的单词数总和最多。
我的想法是用两次动态规划，第一次设置一个数组cnt_word[i][j]（不要吐槽为什么名字那么长）
它表示从i号到j号包含多少单词数，然后就很好推,如果从i号到j号有以i号为头的字母，那么cnt_word[i][j]=cnt_word[i+1][j]+1,
如果不存在,那么就是cnt_word[i][j]=cnt_word[i+1],
可以用strstr来判断是否包含，并且判断是否以a[i]开头，
接下来就很好推了，就是枚举枚举区间。
注意第一个细节，字符串编号是从0开始，那么，范围应是0-（p*20-1），
第二，枚举区间时要注意，不要让某个区间为空，那样一定会错（如果没错，不要拆穿我。）
好了，看不懂的看我代码吧，我会加上注释。
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <string>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int cnt_hang=,cnt_fen=,cnt_words=;
char a[];
char words[][];
int cd_words[]={};//记录每个单词的长度
int cnt_word[][]={};//表示从某开头到某时，能有多少单词.
int jiyi[][]={};
void jilv( );
int cha(int ks,int js);
int dg(int ks,int fen); void jilv( ){
for(int y=cnt_hang*-;y>=;y--)//注意范围
for(int x=y;x>=;x--){
if(cha(x,y)!=)cnt_word[x][y]=cnt_word[x+][y]+;
else cnt_word[x][y]=cnt_word[x+][y];
}
return;
} int cha(int ks,int js){
for(int x=;x<=cnt_words;x++){
char *p=strstr(&a[ks],words[x]);
//表示询问单词x是否是从a[ks]到结束这一段的字符的字串.如果不是,会返回0,如果是 就会返回str2在str1中首次出现的地址
if(p!=&&p-&a[ks]==&&cd_words[x]<=js-ks+)return ;
//如果是字串,且是以a[ks]的字串,并且是在ks到js这一段以内的字串,那么就返回1,
}
return ;
} int dg(int ks,int fen){
//不要吐槽我为什么不用递推,这下面就很好理解了,就是枚举区间.
if(fen==)return cnt_word[ks][cnt_hang*-];
if(jiyi[ks][fen]!=-)return jiyi[ks][fen];
for(int x=ks;x<=cnt_hang*-fen;x++)
jiyi[ks][fen]=max(jiyi[ks][fen],dg(x+,fen-)+cnt_word[ks][x]);
return jiyi[ks][fen];
} int main(int argc, char *argv[]) {
cin>>cnt_hang>>cnt_fen;
cin>>a;
for(int x=;x<=cnt_hang;x++){
char b[];
cin>>b;
strcat(a,b);//表示将b接在a串后面. 注,大多str开头的函数都必须用<cstring>的头文件
}
//cout<<a<<endl;
cin>>cnt_words;
for(int x=;x<=cnt_words;x++){
cin>>words[x];
cd_words[x]=strlen(words[x]);//表示计算长度
}
jilv( );//第一个动归
memset(jiyi,-,sizeof(jiyi));
int ans=dg(,cnt_fen); //就是一个枚举区间
cout<<ans;
return ;
}