POJ 3691 (AC自动机+状态压缩DP)

题目链接:  http://poj.org/problem?id=3691

题目大意：给定N个致病DNA片段以及一个最终DNA片段。问最终DNA片段最少修改多少个字符，使得不包含任一致病DNA。

解题思路：

首先说一下AC自动机在本题中的作用。

①字典树部分：负责判断当前0~i个字符组成的串是否包含致病DNA，这部分靠字典树上的cnt标记完成。

②匹配部分：主要依赖于匹配和失配转移关系的计算，这部分非常重要，用来构建不同字符间状态压缩的转移关系（代替反人类的位运算）。

这也是必须使用AC自动机而不单单是字典树的原因。

 

本题的状态压缩DP思路：

因为是求最少修改的字符。我们把最终DNA片段从第一个字符开始，先枚举字典树中所有字符，作为pre状态。

然后枚举四种修改方案，作为now状态，如果该方案与当前字符的值不同，则次数+1。

如果是致病DNA则跳过。

通过一个Trie的数组池(pool)确定(0<k<4)四种修改方案之后的转移点t的位置，t=pos->next[k]-pool

这样dp[now][t]=min(dp[now][t],dp[pre][j]+0 or 1)

本来的转移方程应该是dp[i][t]=min(dp[i][t],dp[i-1][j]+0 or 1) ，这里感谢zcwwzdjn大神提供的一个滚动数组的优化，也就是now和pre的使用。

同时他的动态AC自动机的变相静态写法也很独特, 主要是pool数组用来确定字符在字典树中标号，弥补了动态写法的不足。

 

#include "cstdio"
#include "string"
#include "queue"
#include "cstring"
#include "iostream"
using namespace std;
#define maxn 55*25
#define inf 0x3f3f3f3f
struct Trie
{
    Trie *next[4],*fail;
    int cnt;
}pool[maxn],*root,*sz;
int dp[2][maxn],now,pre;
Trie *newnode()
{
    Trie *ret=sz++;
    memset(ret->next,0,sizeof(ret->next));
    ret->fail=0;
    ret->cnt=0;
    return ret;
}
int idx(char c)
{
    if(c=='A') return 0;
    if(c=='G') return 1;
    if(c=='C') return 2;
    if(c=='T') return 3;
}
void Insert(string str)
{
    Trie *pos=root;
    for(int i=0;i<str.size();i++)
    {
        int c=idx(str[i]);
        if(!pos->next[c]) pos->next[c]=newnode();
        pos=pos->next[c];
    }
    pos->cnt++;
}
void getfail()
{
    queue<Trie *> Q;
    for(int c=0;c<4;c++)
    {
        if(root->next[c])
        {
            root->next[c]->fail=root;
            Q.push(root->next[c]);
        }
        else root->next[c]=root;
    }
    while(!Q.empty())
    {
        Trie *x=Q.front();Q.pop();
        for(int c=0;c<4;c++)
        {
            if(x->next[c])
            {
                x->next[c]->fail=x->fail->next[c];
                x->next[c]->cnt+=x->fail->next[c]->cnt;
                Q.push(x->next[c]);
            }
            else x->next[c]=x->fail->next[c];
        }
    }
}
void init()
{
    sz=pool; //reset
    root=newnode();
}
int main()
{
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    int n,no=0;
    string tt;
    while(cin>>n&&n)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            cin>>tt;
            Insert(tt);
        }
        getfail();
        cin>>tt;
        int cnt=sz-pool;
        now=0,pre=1;
        memset(dp,0x3f,sizeof(dp));
        dp[now][0]=0;
        for(int i=0;i<tt.size();i++)
        {
            now^=1,pre^=1;
            memset(dp[now], 0x3f, sizeof(dp[now]));
            for(int j=0;j<cnt;j++)
            {
                if(dp[pre][j]<inf)
                {
                    Trie *pos=pool+j;
                    for(int k=0;k<4;k++)
                    {
                        if(pos->next[k]->cnt) continue;
                        int t=pos->next[k]-pool;
                        int add=idx(tt[i])==k?0:1;
                        dp[now][t]=min(dp[now][t],dp[pre][j]+add);
                    }
                }
            }
        }
        int ans=inf;
        for(int i=0;i<cnt;i++) ans=min(ans,dp[now][i]);
        if(ans==inf) printf("Case %d: -1
",++no);
        else  printf("Case %d: %d
",++no,ans);
    }
}

13518359

neopenx

3691

Accepted

232K

63MS

C++

2696B

2014-10-10 22:10:31