题目大意：
给定两个长度分别为 n 和 m 的字符串 A 和 B，选取 A 中的 k 个子串，使这 k 个子串按照先后顺序连接起来后等于 B 子串。
首先，看题目的要求。对于这类题目要求，以及如此之小的数据范围，考虑使用动态规划。
设计状态（需要记录什么？）：
1、A串匹配到哪里
2、B串匹配到哪里
3、当前已经用了多少子配串（k）
4、上一位和这一位选还是不选（会影响到k，于是必须记录）
于是，设计状态 f[i][j][p][0/1]， 来表示A串匹配到 i 位， B串匹配到 j 位， 已经使用了 p 个子串，这一位选/不选的最大方案数。
然后想状态方程：
如果啊 a[i] == b[j]
那么有 f[i][j][p][0] = f[i - 1][j][p][0] + f[i - 1][j][p][1] ; （即为上一位选和不选之和）
f[i][j][1] = f[i-1][j-1][p][1] + f[i-1][j-1][p-1][1] + f[i-1][j-1][p-1][0] ;
如果不相等，
不选的情况和上面一样： f[i][j][p][0] = f[i - 1][j][p][0] + f[i - 1][j][p][1] ;
对于选择的情况，两个不一样，肯定不能选 所以 f[i][j][p][1] = 0;
如此开数组，内存有点吃不消。（起码比赛的时候不敢开到8 * 107）的int数组。
观察一下状态方程，发现我们的 i 这一维， 永远都是i - 1, 也就是说，之前用过的有很大程度上是浪费的。
于是我们用 ^ 操作让这一维滚动起来。
千少万少，代码不能少
#include <bits/stdc++.h> #define N 1010 #define M 210 #define isdigit(c) ((c)>=‘0‘&&(c)<=‘9‘) const int mod = (int)(1e9)+7; using namespace std; int f[2][M][M][2]; char a[N],b[M]; int n, m, k; bool flag = 1; inline int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == ‘-‘) s = -1; c = getchar(); } while(isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ ‘0‘); c = getchar(); } return x * s; } int main(){ n = read(), m = read(), k = read(); scanf("%s%s",a + 1, b + 1); /*一定要从第一位开始，而不能从0开始，不然之后会造成数组越界*/ f[0][0][0][0] = f[1][0][0][0] = 1; for(int i = 1;i <= n; i++, flag ^= 1){ for(int j = 1;j <= m; j++){ for(int p = 1;p <= k; p++){ if(a[i] == b[j]){ f[flag][j][p][0] = (f[flag^1][j][p][0] % mod + f[flag^1][j][p][1] % mod) % mod; f[flag][j][p][1] = (f[flag^1][j-1][p][1] % mod + (f[flag^1][j-1][p-1][0] + f[flag^1][j-1][p-1][1]) % mod) % mod; } else{ f[flag][j][p][0] = ((f[flag^1][j][p][0] + f[flag^1][j][p][1]) % mod); f[flag][j][p][1] = 0; } } } } printf("%d\n",(f[n&1][m][k][0] + f[n&1][m][k][1]) % mod);/*用n的奇偶来判断滚动维度最后是 1 还是 0*/ return 0; }
子串 NOIP2015 D2T2 luoguP2679 字符串处理+DP
原文：https://www.cnblogs.com/wondering-world/p/12770909.html