HDU 4899 Hero meet devil

训练赛的DP套DP，关于DP套DP，以前记得好像做过一道。题目本身十分巧妙，但貌似不是很多。可能不是很好出题吧。
所谓DP套DP，就是我DP所需的状态也需要额外的DP求出来。简单说，就是我需要DP两次，在第一次的DP结果上再DP一次。

题意：
给你一个DNA序列，再给你一个固定长度，问你在这个长度下的所有序列中，与给定的DNA序列的LCS分别为( [0,len(DNA)] )的序列数量。

思路：
因为数据很小，我们可以考虑用状压做。
对于当前长度的一个最优状态，如果增加一个字符，它的下一个状态就需要加上当前状态的序列数量。
这是一个非常常见的计数DP。

但是已知当前状态，无法直接得出下一个状态，而这个就是我们需要嵌套在内的DP了。
我们枚举每一个状态，在枚举每一个字符，使其插入当前状态，再转移它的LCS，最后再统计一下就可以了。
而统计方法是如果当前位置的LCS与前一位置的LCS不同，则说明这个位置与LCS的DNA序列匹配。

虽然我说的很简洁，但是我当时也是想了好长时间……

AC Code

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int maxl = 16;
const int maxs = 1 << maxl;

char key[] = "ATCG";
size_t len;
int dp[2][maxs], ans[maxl];
int nexts[maxs][4];
int pre, cur = 1;
int cnt[maxl], lcs[maxl];

char str[maxl];

inline void add(int &a, int b) {
    a = a + b >= mod ? a + b - mod : a + b;
}

void init() {
    for (int sta = 0; sta < (1 << len); sta++) {
        for (int i = 1; i <= len; i++)
            cnt[i] = cnt[i - 1] + (sta >> (i - 1) & 1);
        for (int k = 0; k < 4; k++) {
            for (int i = 1; i <= len; i++) {
                if (str[i] == key[k])
                    lcs[i] = cnt[i - 1] + 1;
                else
                    lcs[i] = max(lcs[i - 1], cnt[i]);
            }
            int &tmp = nexts[sta][k] = 0;
            for (int i = 1; i <= len; i++)
                tmp |= ((lcs[i] != lcs[i - 1]) << (i - 1));
        }
    }
    memset(dp, 0, sizeof dp);
    memset(ans, 0, sizeof ans);
}

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %d", str + 1, &n);
        len = strlen(str + 1);
        init();
        dp[pre][0] = 1;
        for (int i = 0; i < n; i++) {
            memset(dp[cur], 0, sizeof dp[cur]);
            for (int sta = 0; sta < (1 << len); sta++)
                for (int j = 0; j < 4; j++)
                    add(dp[cur][nexts[sta][j]],dp[pre][sta]);
            cur ^= 1, pre ^= 1;
        }
        for (int sta = 0; sta < (1 << len); sta++)
            add(ans[__builtin_popcount(sta)], dp[pre][sta]);
        for (int i = 0; i <= len; i++)
            printf("%d\n", ans[i]);
    }
    return 0;
}