HDU 2457 DNA repair

好题。但kuangbin说这道题已经是很简单的DP了。
首先kuangbin并没有说错，但是该题的解题思维有点难想到。
如果你按照题意去解题，那你是想不出来的。

还是重在转化啊…………

题意：
给你很多串DNA病毒序列，再给你一串待修复的DNA序列。现在待修复的DNA序列中可能包含病毒序列。
我们的工作是要求修改最少的次数使得待修改序列中不含病毒序列。
问最少次数。

思路：
不要想着去寻找如何修改，有个简单的思路是去寻找所有不含病毒序列的DNA序列，并求出与原串不同的字符数量。然后找出最小值。
但这显然复杂度是很高的。我们可以考虑用DP求解。
记( dp \left[ len \right] \left[ status \right] ) 为当前长度为len，状态结点为 status 时需要修改的最少次数。
那么对下一状态，我对于下面四个结点，如果所组成的字符串构成了病毒串，那么不成立，否则如果当前字符与原字符串当前位置相同，则不需要花费。否则，需要改变一次，花费 + 1。
转移方程
$ dp\left[ len + 1 \right] \left[ NewStatus \right] = \min \left( dp\left[ len + 1 \right] \left[ NewStatus \right] , dp\left[len \right] \left[ OldStatus\right] + str\left[ len \right] \neq next\left[ OldStatus \right] \left[ k \right] \right)$

这里顺便吐槽一下，网上很多题解，就给了转移方程，完全没解释，淦，他们真的懂么……

AC Code

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

#define ll long long

using namespace std;

const int inf = 0x3f3f3f3f;
const int max_n = 1005;
const int max_c = 4;

int dp[max_n][max_n];

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

    inline int getChar(char c)
    {
        if (c == 'A')
            return 0;
        if (c == 'T')
            return 1;
        if (c == 'C')
            return 2;
        return 3;
    }

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

    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 = getChar(str[i]);
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now] = true;
    }

    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();
            if (end[fail[now]])
                end[now] = true;
            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]);
                }
        }
    }

    void solve(int cas, char* str)
    {
        int len = strlen(str);
        for (int i = 0; i <= len; i++)
            for (int j = 0; j < size; j++)
                dp[i][j] = inf;
        dp[0][root] = 0;
        for (int i = 0; i < len; i++)
            for (int j = 1; j < size; j++) {
                if (dp[i][j] < inf) {
                    for (int k = 0; k < max_c; k++) {
                        int ns = next[j][k];
                        if (end[ns])
                            continue;
                        int tmp = k == getChar(str[i]) ? dp[i][j] : dp[i][j] + 1;
                        dp[i + 1][ns] = min(dp[i + 1][ns], tmp);
                    }
                }
            }
        int ans = inf;
        for (int i = 1; i < size; i++)
            ans = min(ans, dp[len][i]);
        printf("Case %d: %d\n", cas, ans == inf ? -1 : ans);
    }
} aho;

char buf[max_n];

int main()
{
    int n, cas = 0;
    while (scanf("%d", &n), n) {
        aho.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", buf);
            aho.insert(buf);
        }
        aho.build();
        scanf("%s", buf);
        aho.solve(++cas, buf);
    }
    return 0;
}