传送门
这道题能看出来是DP。其实这个的状态还是比较好确定的，因为首先我们要从A串中选出一些非空不相交子串，而且他们还必须能按原来的顺序拼成B串，那么我们就知道在枚举到A串第i位，B串第j位的时候，A串前i位中选出的子串肯定是能匹配成B串前j位的。
于是乎我们就有了状态：dp[i][j][k]表示枚举A串到第i位，枚举B串到第j位，已经在A串中选择了k个子串的方案数。这样我们发现还不够，于是又加上一维0/1，表示当前第i位的字符是否选择。（听起来这个和NOIP2016换教室的DP状态有点相似）
之后我就发现自己把状态编出来之后不知道怎么转移……QAQ
这种时候一般怎么考虑？首先因为这个要考虑到两个字符串之间的匹配问题，所以当然是分两种状况，第一种是枚举到的两个字符能匹配，之后再分别转移当前这一位取或者不取，得到如下方程：
dp[i][j][k][0] = dp[i-1][j][k][0] + dp[i-1][j][k][1];
dp[i][j][k][1] = dp[i-1][j-1][k][1] + dp[i-1][j-1][k-1][0] + dp[i-1][j-1][k-1][1];
上面一行还是比较好想的，至于下面一行，我们考虑到当前状态可以是与上一位在同一个被选取的子串中（k不变），这种情况下上一位必须是被选择的，之后再考虑不在同一个子串中的情况即可。
第二种就是枚举的两个字符不匹配，这个就比较好得到如下方程：
dp[i][j][k][0] = dp[i-1][j][k][0] + dp[i-1][j][k][1];
dp[i][j][k][1] = 0;
上面那一行，因为你这一位反正也不取，所以其实是同上的。然后下面这一行因为这一个字符不可取，所以结果为0.
这样我们把过程弄完之后，发现时间复杂度是O（2nmk），这个能过，但是空间复杂度就不行了。但是因为每一位只会用到前一位的状态，所以我们可以直接把第一维滚动掉即可。（这样好像只要2M左右空间就能过了）
初始条件是dp[0][0][0][0] = dp[1][0][0][0] = 1;
好DP题呀……看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 50005; const int mod = 1000000007; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int n,m,k; ll dp[2][205][205][2]; char a[1005],b[205]; int main() { n = read(),m = read(),k = read(); scanf("%s",a+1); scanf("%s",b+1); dp[0][0][0][0] = dp[1][0][0][0] = 1; rep(i,1,n) rep(j,1,m) rep(p,1,k) { int g = i&1; if(a[i] == b[j]) { dp[g][j][p][0] = dp[g^1][j][p][0] + dp[g^1][j][p][1]; dp[g][j][p][0] %= mod; dp[g][j][p][1] = dp[g^1][j-1][p][1] + dp[g^1][j-1][p-1][0] + dp[g^1][j-1][p-1][1]; dp[g][j][p][1] %= mod; } else if(a[i] != b[j]) { dp[g][j][p][0] = dp[g^1][j][p][0] + dp[g^1][j][p][1]; dp[g][j][p][0] %= mod; dp[g][j][p][1] = 0; } } printf("%lld ",(dp[n&1][m][k][0] + dp[n&1][m][k][1]) % mod); return 0; }