NOIP2015 Day2 T2(字符串DP)

发表于 | 分类于 | | + s

这题真的是。。不想说了，刚开始不敢加第三维，然后看题解发现第一维可以压掉。。
然后如果我们设$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]$
注意本题要取模，并且要计算空间复杂度不然会爆炸

#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;
}
------ 本文结束 ------