首页 > 代码库 > POJ 3691 (AC自动机+状态压缩DP）
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 0x3f3f3f3fstruct 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\n",++no); else printf("Case %d: %d\n",++no,ans); }}
POJ 3691 (AC自动机+状态压缩DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。