这个题和之前一个乘法最大思路差不多，就是如果要划分k份之前已经划分了k-1份，划分为k份的就是由，k-1推来的再加上第k份的单词个数，所以就枚举前面k-1分到的位置，是k~当前位置，取最大值，就是结果了
然后单词个数就在线统计就行了，因为以一个数为首字母的只能用一次，所以找最短的单词记下来就行了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char a[999][999],b[9099];int p,k,n;int len[999];int d[99999];
int f[3999][3999];
int main() {
scanf("%d%d",&p,&k);
for(int i=1;i<=p*20;i++)
cin>>b[i];
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
len[i]=strlen(a[i]);
}
d[0]=9999999;
for(int i=1;i<=p*20;i++)
{int minn=99999;int q=9999999;
for(int j=1;j<=n;j++)
{int w=i;int f=0;
for(int k=0;k<len[j];k++)
{
if(b[w++]!=a[j][k])
{
f=1;
break;
}
}
if(f==0)
minn=min(minn,len[j]),q=i+len[j]-1;
}
d[i]=q;
}
for(int i=1;i<=p*20;i++)
for(int j=1;j<=k;j++)
{ int t=0;
for(int q=i;q>=j;q--)
{
if(d[q]<=i) t++;
f[i][j]=max(f[q-1][j-1]+t,f[i][j]);
}
}
printf("%d ",f[p*20][k]);
}