HDU 3341 Lost's revenge

AC自动机 + 变进制状压DP

看题目的 discuss 都说会卡数据，但我还是 1500ms A了。虽然变进制的思路并不是我的……

最近有点懒得写博客了呀

题意：
还是基因碱基对背景。
给你几个模式串，再给你一个匹配串，允许你对匹配串重新排列，要求重新排列后跟模式串匹配的最大数量。

思路：
如果再加个权值，那就是DP套DP了，（误……
本质上还是一个计数DP，考虑状压，但是给定的匹配串长度上限为 40 ，如果开一个状态+节点的 5维数组，会炸内存。
考虑到将节点的 4 维压缩，因为 40 的实际状态数最多是 4 个碱基数量相同的时候。
也就是( 10 \times 10 \times 10 \times 10 )，内存与复杂度均可以承受。

AC Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int max_n = 505;
const int max_c = 4;

int num[4];
int change[130];

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
    }

    void insert(char str[])
    {
        int len = strlen(str), now = root;
        for (int i = 0; i < len; i++) {
            int c = change[(int)str[i]];
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now]++;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            end[now] += end[fail[now]];
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    int dp[max_n][11 * 11 * 11 * 11 + 5];
    int query()
    {
        int res = 0, bit[4];
        memset(dp, -1, sizeof dp), dp[root][0] = 0;
        bit[3] = 1;
        rrange(i, 1, 3) bit[i - 1] = (num[i] + 1) * bit[i];
        range(A, 0, num[0]) range(T, 0, num[1]) range(C, 0, num[2]) range(G, 0, num[3])
        {
            int sta = A * bit[0] + T * bit[1] + C * bit[2] + G;
            range(cur, root, size - 1) if (dp[cur][sta] >= 0) for (int i = 0; i < 4; i++)
            {
                if (i == 0 && A == num[0]) continue;
                if (i == 1 && T == num[1]) continue;
                if (i == 2 && C == num[2]) continue;
                if (i == 3 && G == num[3]) continue;
                dp[next[cur][i]][sta + bit[i]] = max(dp[next[cur][i]][sta + bit[i]], dp[cur][sta] + end[next[cur][i]]);
            }
        }
        int fnl = 0;
        each(i,4) fnl += num[i] * bit[i];
        range(i,root,size - 1) res = max(res, dp[i][fnl]);
        return res;
    }
} aho;

char buf[50];

int main()
{
    change[(int)'A'] = 0, change[(int)'T'] = 1, change[(int)'C'] = 2, change[(int)'G'] = 3;
    int n, cas = 0;
    while (scanf("%d", &n) != EOF && n) {
        memset(num, 0, sizeof num);
        aho.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", buf);
            aho.insert(buf);
        }
        aho.build();
        scanf("%s", buf);
        int len = strlen(buf);
        for (int i = 0; i < len; i++)
            num[change[(int)buf[i]]]++;
        printf("Case %d: %d\n", ++cas, aho.query());
    }
    return 0;
}