首先有暴力dp，令f[i][j][k]表示A中前i个与B中前j个分成k段的方案数，有$f[i][j][k]=\sum_{l=1}^{i}f[i-1][j-l][k-1](A[i-l+1,i]=B[j-l+1,j])$，显然这样时空复杂度都无法承受。
进而考虑优化：l的取值一定是0<l<t，那么只要用前缀和维护一下并不断求出t（如果当前不合法就令t=0，否则t++）；此时空间上就可以直接滚动来优化，最终可以通过。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mod 1000000007
 4 int n,m,t,g[201][201],f[201][201];
 5 char s1[1001],s2[201];
 6 int main(){
 7     scanf("%d%d%d%s%s",&n,&m,&t,s1,s2);
 8     f[0][0]=1;
 9     for(int i=1;i<=n;i++)
10         for(int j=m;j>=1;j--)
11             for(int k=t;k>=1;k--){
12                 if (s1[i-1]==s2[j-1])g[j][k]=(g[j-1][k]+f[j-1][k-1])%mod;
13                 else g[j][k]=0;
14                 f[j][k]=(f[j][k]+g[j][k])%mod;
15             }
16     printf("%d",f[m][t]);
17 }

View Code