原题链接
f[i][j]记录从i分开前面已经分了j份 d[i]是从i这个位置开始到d[i]为一个单词 多于一个时记录最短的一个 wnum[i][j]记录i~j共几个单词 状态转移看代码
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<climits> #include<string> #include<cstdlib> #include<ctime> #define MOD 10007 #define LL long long using namespace std; int i,j,g,p,k,str[205],l[15],fst[15][205],s,d[205],wnum[205][205],f[205][45]; char c[205],words[15][205]; int main() { memset(d,127,sizeof(d)); scanf("%d%d",&p,&k); p=20*p; for(i=1;i<=p;i++) { cin>>c[i]; str[i]=(c[i]-'a')+1; } scanf("%d",&s); for(i=1;i<=s;i++) { scanf("%s",words[i]); l[i]=strlen(words[i]); for(j=0;j<l[i];j++) fst[i][j]=(words[i][j]-'a')+1; } for(i=1;i<=p;i++) for(j=1;j<=s;j++) { int flag=0,b=i; for(g=0;g<l[j];g++) { if(str[b]==fst[j][g]) b++; else {flag=1;break;} } if(!flag) d[i]=min(d[i],i+l[j]-1); } for(i=1;i<=p;i++) for(j=i;j<=p;j++) for(g=i;g<=j;g++) if(d[g]<=j) wnum[i][j]++; for(i=1;i<=p;i++) for(j=1;j<=k;j++) for(g=i-1;g>=j-1;g--) f[i][j]=max(f[i][j],f[g][j-1]+wnum[g+1][i]); printf("%d",f[p][k]); return 0; }