这道题，当时直接把我整懵逼了，结果这两天看了看，顺带搜了下题解，发现居然是一道DP。。我的DP是坠弱的啊。。参考题解，终于搞出来了转移方程。
厚颜无耻地把代码发出来（核心代码基本算是抄的。。）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> const int MOD = 1000000007; using namespace std; char a[1005], b[205]; int n, m, k; int f[2][205][205], s[2][205][205]; int main() { freopen("2015substring.in", "r", stdin); freopen("2015substring.out", "w", stdout); scanf("%d%d%d", &n, &m, &k); scanf("%s%s", a + 1, b + 1); int now = 1, last = 0; s[0][0][0] = 1; for (int i = 1; i <= n; i++) { s[now][0][0] = 1; for (int j = 1; j <= m; j++) { for (int kk = 1; kk <= k; kk++) { if (a[i] == b[j]) { f[now][j][kk] = (f[last][j - 1][kk] + s[last][j - 1][kk -1]) % MOD; } else { f[now][j][kk] = 0; } s[now][j][kk] = (s[last][j][kk] + f[now][j][kk]) % MOD; } } swap(now, last); } printf("%d\n", s[last][m][k]); return 0; } |