[NOIP2015] 子串
题目大意:给出\(a,b\)两个串,可将\(a\)串划分为任意子串,子串按照在\(a\)中出现的次序组合为串\(c\),求有多少\(c\)和\(b\)完全相同
这样子来DP
设\(f[i][j][k]\)为\(a\)串的前\(i\)个匹配\(b\)串的前\(j\)个,用了\(k\)次,且\(a\)串的第\(i\)个一定被选中的方案总数.
设\(s[i][j][k]\)为\(a\)串的前\(i\)个匹配\(b\)串的前\(j\)个,用了\(k\)次,\(a\)串的第\(i\)个不管选没选中的方案总数.
如果\(a_i=b_j\) \(f[i][j][k] = f[i - 1][j - 1][k] + s[i - 1][j - 1][k - 1]\),否则\(f[i][j][k] = 0\)
而无论何时,\(s[i][j][k]=f[i][j][k] + s[i - 1][j][k]\)
滚动数组优化
代码
#include <iostream>
#include <cstdio>
const int N = 1005;
const int Mod = 1000000007;
int n, m, h;
int f[3][205][205], s[3][205][205];
char a[N], b[N];
int main(){
scanf("%d %d %d", &n, &m, &h);
scanf("%s", a + 1);
scanf("%s", b + 1);
int qwq = 1;
f[0][0][0] = s[0][0][0] = 1;//初始化
for(int i = 1; i <= n; ++i, qwq ^= 1){
f[qwq][0][0] = s[qwq][0][0] = 1;//初始化
for(int j = 1; j <= m; ++j)
for(int k = 1; k <= h; ++k){
if(a[i] == b[j])
f[qwq][j][k] = (f[qwq ^ 1][j - 1][k] + s[qwq ^ 1][j - 1][k - 1]) % Mod;
else
f[qwq][j][k] = 0;
s[qwq][j][k] = (f[qwq][j][k] + s[qwq ^ 1][j][k]) % Mod;
}
}
printf("%d\n",s[qwq ^ 1][m][h]);
return 0;
}
按照题意选取最适合的状态来转移