给出一个长度不超过 200 的由小写英文字母组成的字母串(约定;该字串以每行 20 个字母的方式输入，且保证每行一定为 20 个)。要求将此字母串分成 k 份( 1<k≤40 )，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is ，选用 this 之后就不能包含 th )。
单词在给出的一个不超过 6 个单词的字典中。
要求输出最大的个数。
输入格式：
每组的第一行有 2 个正整数( p,k )
p 表示字串的行数, k 表示分为 k 个部分。
接下来的 p 行，每行均有 20 个字符。
再接下来有 1 个正整数 sss ，表示字典中单词个数。( 1≤s≤6 )
接下来的 s 行，每行均有 1 个单词。
输出格式：
1个整数，分别对应每组测试数据的相应结果。
1 3 thisisabookyouareaoh 4 is a ok sab
7
首先一定要夸赞一下水出境界的数据，让我这种蒟蒻用5重循环把这道题水过去了╮(╯▽╰)╭
5重循环后就变成了一道简单dp
f[i][j]表示到第个字符，分成j组后的最大值
f[i][j]=max(f[l-1][j-1]+z[l][i])
每次穷举l然后暴力穷举q（l~i）中每个字母能否作为首字母匹配单词求出z[l][i]
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int i,m,n,j,k,b[10],w,ee,l,q,p,f[201][50],ans,o,v[10001];
char c[201],a[100001],d[10][201];
bool bl;
int main()
{
w=n*20;
for(j=0;j<n;j++)
{
cin>>c;
for(i=0;i<20;i++) a[j*20+i]=c[i];
}
scanf("%d",&m);
for(i=1;i<=m;i++)
{
cin>>d[i];
b[i]=strlen(d[i]);
}
for(i=0;i<w;i++)
for(j=1;j<=min(i,k);j++)
for(l=j-1;l<=i;l++)
{
if(i==5)
{
ee=0;
}
ans=0;
for(q=l;q<=i;q++)
{
bl=0;
for(p=1;p<=m;p++)
{
int t=q,e=0;
while((a[t]==d[p][e])&&(t<=i)&&(e<b[p])) t+=1,e+=1;
if(e==b[p])
{
bl=1;
break;
}
}
if(bl) ans+=1;
}
f[i][j]=max(f[i][j],ans+f[l-1][j-1]);
}
printf("%d\n",f[w-1][k]);
}
原文：https://www.cnblogs.com/ZUTTER/p/9299414.html