题面
有两个仅包含小写英文字母的字符串 A 和 B。
现在要从字符串 A 中取出 k 个互不重叠的非空子串，然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 B 相等？
注意：子串取出的位置不同也认为是不同的方案。
分析
定义f[i][j][p][v]表示从A串的前i位中截取p个子串，去匹配B串的前j位，v表示i这一位选还是不选
因为同一段字符串，例如aab，可被拆成aa和b，也可被拆成a和ab，且如果都能匹配B串，则是两种方案
所以记录i这一位是否选择的信息，可以方便A串划分子串
转移
a[i]==b[j]时
f[i][j][p][0]=f[i-1][j][p][0]+f[i-1][j][p][1]
若要在A的前i位之内匹配B的前j位，第i位又不能选，就只能在前i-1位中匹配完B的前j位
f[i][j][p][1]=f[i-1][j-1][p][1]+f[i-1][j-1][p-1][1]+f[i-1][j-1][p-1][0]
分为两种情况。
大前提是，选择了第i位，则说明前i-1位只需要匹配前j位。
1.把i这一位和第i-1位划分到一个子串内。
所以p的数量是不变的，并且显然i-1必须被选择。-->f[i-1][j-1][p][1]
2.把i这一位不和第i-1位划分到同一个子串内。
则p的数量要腾出来一个，即减一。i-1这一位可选可不选。-->f[i-1][j-1][p-1][1]+f[i-1][j-1][p-1][0]
a[i]!=b[j]时
f[i][j][p][0]=f[i-1][j][p][0]+f[i-1][j][p][1]同理
f[i][j][p][1]=0。因为如果不匹配还选择了这一位，只会使前面匹配的串连上这个字符后完全失效。
空间会有200*200*1000*2=8*1e7
所以考虑空间优化，观察到i这一位只和i-1有关系，所以将第一位滚动。
代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 1010 #define M 210 #define ll long long #define mod 1000000007 bool v=1; int n,m,k; char a[N],b[M]; ll f[2][M][M][2]; int main() { scanf("%d%d%d%s%s",&n,&m,&k,a+1,b+1); f[0][0][0][0]=f[1][0][0][0]=1; for(int i=1;i<=n;i++,v^=1) for(int j=1;j<=m;j++) for(int p=1;p<=k;p++) { f[v][j][p][0]=(f[v^1][j][p][0]+f[v^1][j][p][1])%mod; if(a[i]==b[j]) f[v][j][p][1]=(f[v^1][j-1][p][1]+f[v^1][j-1][p-1][1]+f[v^1][j-1][p-1][0])%mod; else f[v][j][p][1]=0; } printf("%lld ",(f[n&1][m][k][1]+f[n&1][m][k][0])%mod); return 0; }