这个题和之前一个乘法最大思路差不多，就是如果要划分k份之前已经划分了k-1份，划分为k份的就是由，k-1推来的再加上第k份的单词个数，所以就枚举前面k-1分到的位置，是k~当前位置，取最大值，就是结果了 然后单词个数就在线统计就行了，因为以一个数为首字母的只能用一次，所以找最短的单词记下来就行了。
#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]); }