NOIP2015 Day2 T2(字符串DP)

这题真的是。。不想说了,刚开始不敢加第三维,然后看题解发现第一维可以压掉。。
然后如果我们设$f[i,j,k]$为$A$匹配到$i$, $B$匹配到$j$, 已经分了$k$个部分的方案总数,在转移的时候发现不能判断某一个字符取了还是没取,那么加一维, $f[i, j, k, 0]$表示不取,$f[i, j, k, 0]$表示取。
那么分别转移:
$$f[i,j,k,0]=f[i-1,j,k,1]+f[i-1,j,k,0]$$
$$f[i,j,k,1] = f[i-1,j-1,k,1] + f[i-1,j-1,k-1,1] + f[i-1,j-1,k-1,0]$$
在$A[i]==B[j]$时,才能更新$f[i,j,k,1]$
初始化时$f[i,1,1,0] = s​$, $s​$为前$i​$个字符能匹配$B[1]​$多少次,那么每次枚举,都$f[i,1,1,0]=s​$, 如果当前为能够匹配,则$f[i,1,1,1] = 1,s+=1​$
最后答案是$f[n,m,k,0]+f[n,m,k,1]$
注意本题要取模

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 1000 + 5, MAXM = 200 + 5, MO = 1000000007;
int n, m, k;
char a[MAXN], b[MAXM];
LL f[MAXM][MAXM][2], g[MAXM][MAXM][2];
void clean() {
ms(f, 0), ms(g, 0);
}
void init() {
clean();
scanf("%s%s", a+1, b+1);
}
void solve() {
int s = 0;
for (int i=1;i<=n;i++) {
//init
f[1][1][0] = s;
if (a[i]==b[1]) f[1][1][1] = 1, s++;
//start
for (int j=2;j<=m;j++)
for (int kk=1;kk<=k;kk++) {
f[j][kk][0] = (g[j][kk][1]+g[j][kk][0])%MO;
if (a[i]==b[j]) f[j][kk][1] = (g[j-1][kk][1]+g[j-1][kk-1][1]+g[j-1][kk-1][0])%MO;
}
//clean
for (int j=1;j<=m;j++)
for (int kk=1;kk<=k;kk++) {
g[j][kk][0] = f[j][kk][0], f[j][kk][0] = 0;
g[j][kk][1] = f[j][kk][1], f[j][kk][1] = 0;
}
}
printf("%lld\n", (g[m][k][0]+g[m][k][1])%MO);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d%d", &n, &m, &k)==3) init(), solve();
return 0;
}

------ 本文结束 ------