题目链接: 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[],*fail;
int cnt;
}pool[maxn],*root,*sz;
int dp[][maxn],now,pre;
Trie *newnode()
{
Trie *ret=sz++;
memset(ret->next,,sizeof(ret->next));
ret->fail=;
ret->cnt=;
return ret;
}
int idx(char c)
{
if(c=='A') return ;
if(c=='G') return ;
if(c=='C') return ;
if(c=='T') return ;
}
void Insert(string str)
{
Trie *pos=root;
for(int i=;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=;c<;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=;c<;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=;
string tt;
while(cin>>n&&n)
{
init();
for(int i=;i<=n;i++)
{
cin>>tt;
Insert(tt);
}
getfail();
cin>>tt;
int cnt=sz-pool;
now=,pre=;
memset(dp,0x3f,sizeof(dp));
dp[now][]=;
for(int i=;i<tt.size();i++)
{
now^=,pre^=;
memset(dp[now], 0x3f, sizeof(dp[now]));
for(int j=;j<cnt;j++)
{
if(dp[pre][j]<inf)
{
Trie *pos=pool+j;
for(int k=;k<;k++)
{
if(pos->next[k]->cnt) continue;
int t=pos->next[k]-pool;
int add=idx(tt[i])==k?:;
dp[now][t]=min(dp[now][t],dp[pre][j]+add);
}
}
}
}
int ans=inf;
for(int i=;i<cnt;i++) ans=min(ans,dp[now][i]);
if(ans==inf) printf("Case %d: -1\n",++no);
else printf("Case %d: %d\n",++no,ans);
}
}
| 13518359 | neopenx | 3691 | Accepted | 232K | 63MS | C++ | 2696B | 2014-10-10 22:10:31 |