题目描述
给出一个长度不超过 
200 的由小写英文字母组成的字母串（该字串以每行20 个字母的方式输入，且保证每行一定为20 个）。要求将此字母串分成 k 份，且每份中包含的单词个数加起来总数最大。
每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不能包含 th。
单词在给出的一个不超过 6 个单词的字典中。
要求输出最大的个数。
输入格式
每组的第一行有两个正整数 
p,k 
p 表示字串的行数，
k 表示分为k个部分。
接下来的 p 行，每行均有 20 个字符。
再接下来有一个正整数 s，表示字典中单词个数。 接下来的 s 行，每行均有一个单词。
输出格式
1个整数，分别对应每组测试数据的相应结果。
输入输出样例
输入 #1 
复制 
1 3
thisisabookyouareaoh
4
is
a
ok
sab
输出 #1 
复制 
7
说明/提示
【数据范围】
对于
100% 的数据，
2≤k≤40
1≤s≤6。
【样例解释】 划分方案为 this / isabookyoua / reaoh

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long p,k,n;
string s,zs="";
string s2;
string sz[10];
long long f[205][205];//f用来保存一个区间的字符串的个数 
long long cd[205];//名字很显然，长度 
long long dp[205][45];//dp[i][j]表示前i个数分成j份的和最大是多少 
string jq;
long long z;
bool hx(long long wz,long long wz2)//匹配新加入的开头可不可以当一个单词的开头 
{
	for(int i=0;i<n;i++)
	{
		if(wz+cd[i]-1>wz2)//超长了 
		{
			continue;
		}
		jq=zs.substr(wz,cd[i]);//这东西是截取字符串的，用法是substr(截取开始位置,包括开始位置一共截取长度)。 
		if(jq==sz[i])//可以对上！好了有一个单词可以匹配上了，直接结束。 
		{
			return true;
		}
	}
	return false;
}
int main()
{
	cin>>p>>k;
	for(int i=0;i<p;i++)
	{
		cin>>s;
		zs+=s;//zs是真正的字符串 
	}
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>sz[i];
		cd[i]=sz[i].length();//这个是长度，一会截取字符串要用 
	}
	for(int i=p*20-1;i>=0;i--)//上面讲过的模拟策略 
	{
		for(int j=i;j>=0;j--)
		{
			f[j][i]+=f[j+1][i];//后面的要继承上 
			if(hx(j,i)==true)//因为不能有开头重合的字符串，所以一个开头最多选一个，因此只要有一个匹配我们就选他就可以了。 
			{
				f[j][i]++;
			}
		}
	}
	for(int i=0;i<=p*20-1;i++)//i是开头 
	{
		for(int j=1;j<=k;j++)//j是分成j块（我之前就是把j初始值定义成0所以wa了一次。 
		{
			if(j==1)//这个值已经知道了，直接赋值 
			{
				dp[i][j]=f[0][i];
			}else
			{
				for(int u=j+1;u<i;u++)//开始枚举分割点 
				{
					dp[i][j]=max(dp[i][j],dp[u][j-1]+f[u+1][i]);//这一段要分裂成j块，可以看成从0到u的一大块分成j-1块，再加上u后面到i不分割，然后这个方程就出来了。 
				}	
			}
		}
	}
	cout<<dp[p*20-1][k]<<endl;//输出 完结撒花 
	return 0;
}