感觉是最长公共子序列模型的变式。
容易想到记 \(f[i][j][k]\) 表示 \(A\) 走到了第 \(i\) 位，\(B\) 匹配上了 \(1 \sim j\)，目前分成了 \(k\) 段的方案数。
如果强制第 \(i\) 位必须匹配上的话，需要枚举位置 \(p\)，满足 \(A[p] = B[j - 1]\)。这样的复杂度是 \(O(n^2m^2)\)，无法通过本题。
我们采用类似最长公共子序列的方式，不必强制 \(i\) 必须匹配上，也可以直接从上一个状态继承过来。
具体来说，记 \(f[i][j][k][1/0]\) 表示 \(A\) 走到了第 \(i\) 位，\(B\) 匹配上了 \(1 \sim j\)，目前分成了 \(k\) 段，\(a[i]\) 匹配 / 不匹配的方案数。
如果 \(a[i]\) 匹配上了，分段的话，上一位匹没匹配上无所谓，不分段的话，上一位也必须要匹配上，即：
\[f[i][j][k][1] = f[i - 1][j - 1][k - 1][0] + f[i - 1][j - 1][k - 1][1] + f[i - 1][j - 1][k ][1] \]如果 \(a[i]\) 没匹配上，上一位匹没匹配上无所谓，即：
\[f[i][j][k][0] = f[i - 1][j][k][0] + f[i - 1][j][k][1] \]答案就是 \(f[n][m][k][0] + f[n][m][k][1]\)。注意有上一位的继承，所以不用枚举谁匹配 \(b[m]\) 了。
时间复杂度 \(O(nm^2)\)，而且跑不满，非常快。
算一下空间，\(128MB\) 存不下，把 \(i\) 维给滚掉就可以了。
（今天才发现原来 Luogu 不能 cin >> (a + 1)，于是用了 scanf）
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
int f[2][205][205][2];
int n, m, s;
char a[1005], b[205];
signed main(){
scanf("%d %d %d %s %s", &n, &m, &s, a + 1, b + 1);
F(i, 1, n){
f[(i - 1) & 1][0][0][0] = 1;
F(j, 1, m) F(k, 1, s) f[i & 1][j][k][0] = f[i & 1][j][k][1] = 0;
F(j, 1, min(i, m)){
F(k, 1, min(j, s)){
f[i & 1][j][k][0] = (f[(i - 1) & 1][j][k][0] + f[(i - 1) & 1][j][k][1]) % mod;
if(a[i] == b[j])
f[i & 1][j][k][1] = ((f[(i - 1) & 1][j - 1][k][1]+ f[(i - 1) & 1][j - 1][k - 1][0]) % mod + f[(i - 1) & 1][j - 1][k - 1][1]) % mod;
}
}
}
printf("%d", (f[n & 1][m][s][0] + f[n & 1][m][s][1]) % mod);
return fflush(0), 0;
}
本题的关键在于打开思路，不必强制当前位必须匹配，一个小小的定义修改，足以影响复杂度。
标签：子串,NOIP2015,匹配,int,提高,205,复杂度,mod From： https://www.cnblogs.com/superl61/p/18518625