POJ-3691 DNA repair ACオートマトン+DP
20282 ワード
タイトルリンク:http://poj.org/problem?id=3691
まず1 Aを祝う.
単一列のマッチングであれば,状態遷移方程式はf[i][j]であり,マッチング列の上位iビットの最近の9桁の状態がjの最小変更であることを示し,各状態を状態圧縮で表すとよい.複雑さは指数級であり,小さい文字列に対しては許容できる.しかし、これは多くの不必要な場合があり、多くの遷移がまとめられるため、すなわち修正または修正されないため、方程式をマッチング列のi番目がテンプレート列のj番目のノードであることを示す最適解に変更すると、各ノードに対して4つの遷移状態、すなわち1つの単列のDFAしかない.同様に,複数の列に対して1つのACオートマチックを確立すればよい,遷移方程式:f[i][j]=Min{f[i][j],f[i][son]+c!=id}である.
注意現在の列の文字列が不正な列である場合を考慮してください.
まず1 Aを祝う.
単一列のマッチングであれば,状態遷移方程式はf[i][j]であり,マッチング列の上位iビットの最近の9桁の状態がjの最小変更であることを示し,各状態を状態圧縮で表すとよい.複雑さは指数級であり,小さい文字列に対しては許容できる.しかし、これは多くの不必要な場合があり、多くの遷移がまとめられるため、すなわち修正または修正されないため、方程式をマッチング列のi番目がテンプレート列のj番目のノードであることを示す最適解に変更すると、各ノードに対して4つの遷移状態、すなわち1つの単列のDFAしかない.同様に,複数の列に対して1つのACオートマチックを確立すればよい,遷移方程式:f[i][j]=Min{f[i][j],f[i][son]+c!=id}である.
注意現在の列の文字列が不正な列である場合を考慮してください.
1 //STATUS:C++_AC_79MS_4200KB
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #include<math.h>
6 #include<iostream>
7 #include<string>
8 #include<algorithm>
9 #include<vector>
10 #include<queue>
11 #include<stack>
12 #include<map>
13 #include<set>
14 using namespace std;
15 //define
16 #define pii pair<int,int>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 #define PI acos(-1.0)
21 //typedef
22 typedef __int64 LL;
23 typedef unsigned __int64 ULL;
24 //const
25 const int N=1010;
26 const int INF=0x3f3f3f3f;
27 const int MOD=100000,STA=8000010;
28 const LL LNF=1LL<<60;
29 const double EPS=1e-8;
30 const double OO=1e15;
31 //Daily Use ...
32 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
33 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
34 template<class T> inline T Min(T a,T b){return a<b?a:b;}
35 template<class T> inline T Max(T a,T b){return a>b?a:b;}
36 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
37 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
38 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
39 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
40 //End
41
42 char s[N];
43 int idx[100];
44 int ch[N][4];
45 int val[N],f[N],dp[N][N],sta[N],ma[N];
46 int sz,n,cnt;
47
48 void init(){sz=1;mem(ch[0],0);}
49
50 void insert(char *s,int v){
51 int i,len=strlen(s),id,u=0;
52 for(i=0;i<len;i++){
53 id=idx[s[i]];
54 if(!ch[u][id]){
55 mem(ch[sz],0);
56 val[sz]=0;
57 ch[u][id]=sz++;
58 }
59 u=ch[u][id];
60 }
61 val[u]=v;
62 }
63
64 void getFail()
65 {
66 int c,u,r;
67 queue<int> q;
68 f[0]=0;
69 ma[0]=0;sta[0]=cnt++;
70 for(c=0;c<4;c++){
71 u=ch[0][c];
72 if(u){
73 if(!val[u])ma[u]=cnt;sta[cnt++]=u;
74 f[u]=0;
75 q.push(u);
76 }
77 }
78 while(!q.empty()){
79 r=q.front();q.pop();
80 for(c=0;c<4;c++){
81 u=ch[r][c];
82 if(!u){
83 ch[r][c]=ch[f[r]][c];
84 continue;
85 }
86 q.push(u);
87 f[u]=ch[f[r]][c];
88 if(val[r] || val[f[u]])val[u]=1;
89 if(!val[u]){ma[u]=cnt;sta[cnt++]=u;}
90 }
91 }
92 }
93
94 int main()
95 {
96 // freopen("in.txt","r",stdin);
97 int i,j,t,c,test=1,ans,len,ok,id,u;
98 char temp[23];
99 idx['A']=0;idx['C']=1;idx['T']=2,idx['G']=3;
100 while(~scanf("%d",&n) && n)
101 {
102 init();
103 for(i=0;i<n;i++){
104 scanf("%s",temp);
105 insert(temp,1);
106 }
107 scanf("%s",s);
108 len=strlen(s);
109
110 cnt=0;
111 mem(dp,INF);
112 dp[0][0]=0;
113 getFail();
114 for(i=0;i<len;i++){
115 ok=0;
116 id=idx[s[i]];
117 for(j=0;j<cnt;j++){
118 if(dp[i][j]==INF)continue;
119 for(c=0;c<4;c++){
120 u=ch[sta[j]][c];
121 t=(c!=id);
122 if(!val[u]){
123 ok=1;
124 dp[i+1][ma[u]]=Min(dp[i+1][ma[u]],dp[i][j]+t);
125 }
126 }
127 }
128 if(!ok)break;
129 }
130
131 if(ok){
132 ans=INF;
133 for(i=0;i<cnt;i++){
134 ans=Min(ans,dp[len][i]);
135 }
136 }
137 else ans=-1;
138
139 printf("Case %d: %d
",test++,ans);
140 }
141 return 0;
142 }