https://www.luogu.org/problem/show?pid=1026#sub 点：同一字母不能重复用做首字母。 首先，处理出数组w[i][j] ,表示从i到j有多少个单词（当以同一个字母为首字母时，越短越好）。 然后，求出d[i]，表示以i开头的最短单词的结尾的位置。 数组f[i][j]表示以i为终点，分为j份最多单词数。 然后状态转移方程： f[i][j]=max(f[i][j],f[k][j-1]+w[k+1][i]) (j-1<=k<=i-1)
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int w[209][209],n,m,s; int a[209],d[209],f[209][209]; struct word{ int l; int c[201]; }b[10]; int comp(const word&x,const word&y) { return x.l<y.l?1:0; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=20*n;i++) { char c; cin>>c; a[i]=c-'a'+1; } scanf("%d",&s); for(int i=1;i<=s;i++) { char c[201]; cin>>c; for(int j=0;j<strlen(c);j++) b[i].c[j+1]=c[j]-'a'+1; b[i].l=strlen(c); } sort(b+1,b+s+1,comp); for(int i=1;i<=20*n;i++) { for(int j=1;j<=s;j++) { int p=0; for(int k=1;k<=b[j].l;k++) { int t=i+k-1; if(a[t]!=b[j].c[k]) p=1; } if(!p) {d[i]=i+b[j].l-1; break;} } } for(int i=1;i<=20*n;i++) { for(int j=i;j<=20*n;j++) { for(int p=i;p<=j;p++) if(d[p]<=j&&d[p]) w[i][j]++; } } for(int i=1;i<=20*n;i++) for(int j=1;j<=m;j++){ for(int k=j-1;k<=i-1;k++) f[i][j]=max(f[i][j],f[k][j-1]+w[k+1][i]); } printf("%d",f[20*n][m]); return 0; }