HDU - 2457-DNA repair(AC自动机, DP)

链接:

https://vjudge.net/problem/HDU-2457

题意:

Biologists finally invent techniques of repairing DNA that contains segments causing kinds of inherited diseases. For the sake of simplicity, a DNA is represented as a string containing characters 'A', 'G' , 'C' and 'T'. The repairing techniques are simply to change some characters to eliminate all segments causing diseases. For example, we can repair a DNA "AAGCAG" to "AGGCAC" to eliminate the initial causing disease segments "AAG", "AGC" and "CAG" by changing two characters. Note that the repaired DNA can still contain only characters 'A', 'G', 'C' and 'T'.

You are to help the biologists to repair a DNA by changing least number of characters.

思路:

DP,但是是在trie图上跑, 跟找没有模板穿串很像,构造出一个跟给的串差别最小的.
DP[i][j], 表示长度i,以j节点结尾,不包含模板串的最小操作, 对某个节点,向下扩展一个判断在原串上是否需要修改, 选一个最小的.
注意,fail节点指向的点的状态要向下更新, 忘记更新wa了好久..

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
//#include <memory.h>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <stack>
#include <string>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <sstream>
#define MINF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const LL MOD = 20090717;
const LL MAXN = 2e6+10;
const int MAXASCII = 4;

struct TrieTree
{
    int Next[MAXASCII];
    int end;
    int fail;
    void Clear()
    {
        memset(Next, 0, sizeof(Next));
        end = 0;
        fail = 0;
    }
}tree[MAXN];

char s[MAXN];
int Dp[1010][1010];
map<char, int> Mp;
int n, m, k, cnt;

void Insert(char *s)
{
    int len = strlen(s);
    int p = 0;
    for (int i = 0;i < len;i++)
    {
        if (tree[p].Next[Mp[s[i]]] == 0)
            tree[p].Next[Mp[s[i]]] = ++cnt, tree[cnt].Clear();
        p = tree[p].Next[Mp[s[i]]];
    }
    tree[p].end = 1;
}

void BuildAC()
{
    queue<int> que;
    for (int i = 0;i < MAXASCII;i++)
    {
        if (tree[0].Next[i] != 0)
        {
            tree[tree[0].Next[i]].fail = 0;
            que.push(tree[0].Next[i]);
        }
    }
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        if (tree[tree[u].fail].end)
            tree[u].end = 1;
        for (int i = 0;i < MAXASCII;i++)
        {
            if (tree[u].Next[i] != 0)
            {
                tree[tree[u].Next[i]].fail = tree[tree[u].fail].Next[i];
                que.push(tree[u].Next[i]);
            }
            else
                tree[u].Next[i] = tree[tree[u].fail].Next[i];
        }
    }
}

int Solve()
{
    int len = strlen(s+1);
    memset(Dp, MINF, sizeof(Dp));
    Dp[0][0] = 0;
    for (int i = 0;i < len;i++)
    {
        for (int j = 0;j < cnt;j++)
        {
            if (Dp[i][j] == MINF)
                continue;
            for (int t = 0;t < 4;t++)
            {
                if (tree[tree[j].Next[t]].end == 1)
                    continue;
                int tmp = Dp[i][j] + (Mp[s[i+1]] == t?0:1);
                Dp[i+1][tree[j].Next[t]] = min(Dp[i+1][tree[j].Next[t]], tmp);
            }
        }
    }
    int tmp = MINF;
    for (int i = 0;i <= cnt;i++)
        tmp = min(tmp, Dp[len][i]);
    return ((tmp == MINF)?-1:tmp);
}

int main()
{
    Mp['A'] = 0;
    Mp['T'] = 1;
    Mp['G'] = 2;
    Mp['C'] = 3;
    int testcnt = 0;
    while (~scanf("%d", &n) && n)
    {
        cnt = 0;
        tree[cnt].Clear();
        for (int i = 1;i <= n;i++)
        {
            scanf("%s", s);
            Insert(s);
        }
        scanf("%s", s+1);
        BuildAC();
        printf("Case %d: %d\n", ++testcnt, Solve());
    }

    return 0;
}