摘要：
标题描述给出了一个由长度不超过200的小写英文字母组成的字母串。该单词在字典中给出，不超过6个单词。需要最大输出数。接下来的p行各有20个字符。然后是一个正整数s，它表示字典中的单词数。解析：首先，我们需要将整个字符串中的每个单词标记为1，然后我们需要执行第一个DP——推导任何一个片段中的最大单词数。然后，它与之前山区建学小学的DP完全相同，即找到k个分解点，但这个问题是找到最大数字代码^-^#include #include＜string h＞#include˂algorithm＞usingspacestd；intstr[201][201]，f[201][201]；查尔斯[201]；intmain（）{intT；scanf；而（T--）{intp，k；scanf，intl=20*p；对于{scanf；}整数；扫描；对于{charlc[201]；scanf；intll=strlen；对于{intsf=1，t=j；forif（ls[t]！
题目描述 Description
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)（管理员注：这里的不能再用指的是位置，不是字母本身。比如thisis可以算做包含2个is）。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
输入描述 Input Description
第一行为一个正整数(0<n<=5)表示有n组测试数据
每组的第一行有二个正整数(p，k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)
接下来的s行，每行均有一个单词。
输出描述 Output Description
每行一个整数，分别对应每组测试数据的相应结果。
样例输入 Sample Input
1
1 3
thisisabookyouareaoh
4
is
a
ok
sab
样例输出 Sample Output
7
数据范围及提示 Data Size & Hint
this/isabookyoua/reaoh
至今我遇到的最皮的动态规划，要用两次DP，而且还与字符串有关（绝望……），但是，还好有学长！
解析：
我们先要把每个单词在整段字符串但凡存在，就把 str[ from ][ to ] 标记为1
然后进行第1次DP——推出任意一段存在的最多单词数
接着，就和先前发的 山区建小学 的DP一模一样，就是找 k 个分解点，只不过本题是 求出最多的数量
代码^-^
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int str[201][201],f[201][201]; char ls[201]; int main() { int T; scanf("%d",&T); while(T--) { int p,k; scanf("%d%d",&p,&k); int l=20*p; for(int i=0;i<p;++i){ scanf("%s",ls+i*20); } int s; scanf("%d",&s); for(int i=1;i<=s;++i) { char lc[201]; scanf("%s",lc); int ll=strlen(lc); for(int j=0;j<l;++j) { int sf=1,t=j; for(int o=0;o<ll;++o,++t) if(ls[t]!=lc[o]) { sf=0; break; } if(sf) str[j+1][j+ll]=1; } } for(int j=2;j<=l;++j) for(int i=j-1;i;--i) if(str[i][j]) str[i][j]+=str[i+1][j]; else str[i][j]=str[i+1][j]+str[i][j-1]-str[i+1][j-1]; for(int i=1;i<=l;++i) f[i][1]=str[1][i]; for(int i=2;i<=l;++i) for(int j=2;j<=k && j<=i;++j) for(int q=j-1;q<i;++q) f[i][j]=max(f[i][j],f[q][j-1]+str[q+1][i]); printf("%d",f[l][k]); memset(str,0,sizeof(str)); memset(f,0,sizeof(f)); } return 0; }