HDU4899 Hero meet devil DP套DP

陈老师的题QwQ
原题链接

题目大意

有两个字符串(S)和(T)（都只能由'A','C','G','T'这四个字符组成），(S)已知(T)未知，还知道(S)的长度为(m)。求满足(Len(LCS(S,T))=L,1leqslant Lleqslant |T|)的(S)的个数
先想想若(S)已知怎么做。一个简单的(DP)就能解决，设(dp[i][j])表示(S)到(i)位置，(T)到(j)位置时(LCS)的长度：
1.若(S[i]==T[j])，则(dp[i][j]=max(dp[i-1][j-1]+1,max(dp[i-1][j],dp[i][j-1])))
2.否则(dp[i][j]=max(dp[i-1][j],dp[i][j-1]))
然后考虑倒过来怎么做，看一下数据范围，可能状压？设(f[i][state])表示(T)填到第(i)位，(dp[?][i])在(Len(S)+1)进制下的表示时的方案数，再令(g[state][c])表示状态是(state)时再加一个字符(c)后的(state)是多少。(g)数组可以预处理一下，然后(f)就好转移了：
(f[i][g[state][c]]=f[i][g[state][c]]+f[i-1][state])
这样的话空间显然会炸，一个显然的性质，(dp[i][j])只有可能是(dp[i-1][j])或(dp[i-1][j]+1)，我们把差分数组在二进制下压一下就行了
预处理时间复杂度(O(4*n*2^{Len(S)}))，转移的时间复杂度为(O(4*m*2^{Len(S)}))，空间复杂度( heta (m*2^{Len(S)}+4*2^{Len(S)}))
代码（预处理参考了自为风月马前卒大佬的博客）：

#include <bits/stdc++.h>

#define MOD 1000000007

using namespace std;

int kase;
string S;
char ch[4] = {'A', 'C', 'G', 'T'};
int n, m, tmp[2][20], lim, f[1001][32800], g[32800][4], ans[20];

int lowbit(int x) {
    return x&-x;
}

int popcount(int x) {
    int cnt = 0;
    while(x) cnt++, x -= lowbit(x);
    return cnt;
}

int calc(int state, char c) {
    for(int i = 1; i <= n; ++i) tmp[0][i] = tmp[0][i-1]+((state>>i-1)&1);
    int ret = 0;
    for(int i = 1; i <= n; ++i)
    {
        int t = 0;
        if(c == S[i-1]) t = tmp[0][i-1]+1;
        t = max(t, max(tmp[1][i-1], tmp[0][i]));
        tmp[1][i] = t;
    }
    for(int i = 1; i <= n; ++i) ret += (1<<i-1)*(tmp[1][i]-tmp[1][i-1]); 
    return ret;
}

int main() {
    cin >> kase;
    for(int i = 1; i <= kase; ++i) {
        cin >> S >> m;
        n = S.length();
        lim = (1<<n)-1;
        memset(f, 0, sizeof f), memset(ans, 0, sizeof ans);
        f[0][0] = 1;
        for(int i = 0; i <= lim; ++i)
            for(int j = 0; j < 4; ++j) g[i][j] = calc(i, ch[j]);
        for(int i = 1; i <= m; ++i)
            for(int j = 0; j <= lim; ++j)
                for(int k = 0; k < 4; ++k)
                    f[i][g[j][k]] = (f[i][g[j][k]]+f[i-1][j])%MOD;
        for(int i = 0; i <= lim; ++i) ans[popcount(i)] = (ans[popcount(i)]+f[m][i])%MOD;
        for(int i = 0; i <= n; ++i) cout << ans[i] << endl;
    }
    return 0;
}