QAQ 话说这个题目跟那个乘号的比较像啊，，，，，，， 用f[i][j]表示前i个字母划分为j段的单词最大数 那么我们很容易就得到一个状态转移方程 f[i][j]=max(f[i][j],f[l-1][j]+w)//w为l-i区间里单词的数目 现在的问题是w咋求 之前我做的一个题是划分乘号的 那个我们处理了一个sum[i][j]数组，表示的是i-j组成的数字 这个题目可以这样处理，但是还有个跟巧妙的方法 处理一个d[i]数组，表示以i为首位置的单词的终点，这个距离肯定越小越好 这样我们再倒着枚举，就可以达到一个很好地效果
#include <cstdio> #include <iostream> #include <cstring> #include <string> using namespace std; char s[99999]; char sn[8][999],len[8]; int d[9999];//以i为首位置的单词的终点 int dp[999][999];//前i个字母划分为j段的单词最大数 int p,m; int t; int screen() { int n=strlen(s+1); memset(d,127,sizeof(d)); for(int i=1;i<=n;i++) for(int j=1;j<=t;j++) { if(n-i+1<len[j]||d[i]<=len[j]) continue; int flag=0; for(int l=0;l<len[j];l++) if(s[i+l]!=sn[j][l+1]) { flag=1; break; } if(flag) continue; d[i]=min(d[i],i+len[j]-1); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int sum=0; for(int l=i;l>=j;l--) { if(d[l]<=i) sum++; dp[i][j]=max(dp[i][j],dp[l-1][j-1]+sum); } } return dp[n][m]; } int main() { scanf("%d%d",&p,&m); for(int i=1;i<=p;i++) scanf("%s",s+1+(i-1)*20); scanf("%d",&t); for(int i=1;i<=t;i++) scanf("%s",sn[i]+1),len[i]=strlen(sn[i]+1); printf("%d",screen()); return 0; }