 | |||||||||||||
| |||||||||||||
| BestCoder官方QQ群：385386683 歡迎加入~ 尋人啟事：2014級新生看過來！ | |||||||||||||
DNA repairTime Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1352 Accepted Submission(s): 734 Problem Description 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. Input The input consists of multiple test cases. Each test case starts with a line containing one integers N (1 ≤ N ≤ 50), which is the number of DNA segments causing inherited diseases. The following N lines gives N non-empty strings of length not greater than 20 containing only characters in "AGCT", which are the DNA segments causing inherited disease. The last line of the test case is a non-empty string of length not greater than 1000 containing only characters in "AGCT", which is the DNA to be repaired. The last test case is followed by a line containing one zeros. Output For each test case, print a line containing the test case number( beginning with 1) followed by the number of characters which need to be changed. If it's impossible to repair the given DNA, print -1. Sample Input |
最近做AC自動機跟DP結合的題，總結一下，首先建構AC自動機，然後根據AC自動機構造轉台轉移，就是說不能往單詞節點轉移，那種構造字元串的題，可以利用矩陣計算，也可以用DP進行計算，還有像這種修改字元串達到要求的，則可以用dp計算。
其實就是利用AC自動機的每個節點作為狀态進行轉移
對于這個題：構造完AC自動機後，進行轉移，遇到單詞節點跳過，不是的話判斷此節點的字母與要比對的串的字母是否相等，相等說明不用修改，否則加1，轉移到下一個節點
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=1010;
const int INF=1000000000;
const int SIGMA_SIZE=4;
int N;
char s[30],str[maxn];
struct AC
{
int ch[maxn][4],val[maxn];
int fail[maxn];
int dp[maxn][maxn];
int sz;
void clear(){memset(ch[0],0,sizeof(ch[0]));sz=1;}
int idx(char x)
{
if(x=='A')return 0;
else if(x=='C')return 1;
else if(x=='G')return 2;
return 3;
}
void insert(char *s)
{
int n=strlen(s);
int u=0;
for(int i=0;i<n;i++)
{
int c=idx(s[i]);
if(!ch[u][c])
{
memset(ch[sz],0,sizeof(ch[sz]));
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=1;
}
void getfail()
{
queue<int> q;
fail[0]=0;
int u=0;
for(int c=0;c<SIGMA_SIZE;c++)
{
u=ch[0][c];
if(u){fail[u]=0;q.push(u);}
}
while(!q.empty())
{
int r=q.front();q.pop();
if(val[fail[r]])val[r]=1;
for(int c=0;c<SIGMA_SIZE;c++)
{
u=ch[r][c];
if(!u){ch[r][c]=ch[fail[r]][c];continue;}
q.push(u);
int v=fail[r];
while(v&&!ch[v][c])v=fail[v];
fail[u]=ch[v][c];
}
}
}
void solve(char *s)
{
int n=strlen(s);
for(int i=0;i<=n;i++)
for(int j=0;j<sz;j++)dp[i][j]=INF;
dp[0][0]=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<sz;j++)
{
for(int k=0;k<4;k++)
{
//剛開始這裡不太明白為什麼單詞節點要跳過去，因為自己覺得也可以修改這個點來維護，後來一想真是自己秀逗了
//跳過去之後，去比對下一個，肯定會修改的（ACGA是單詞節點，目前比對到G了，往下走的時候，發現A是單詞節點，跳過去
//在去比對G的孩子C，C!=A，是以多一次修改，還是相當于修改了A這個點）
if(val[ch[j][k]])continue;
int tmp;
if(k==idx(s[i]))tmp=dp[i][j];
else tmp=dp[i][j]+1;
dp[i+1][ch[j][k]]=min(dp[i+1][ch[j][k]],tmp);
}
}
}
int ans=INF;
for(int i=0;i<sz;i++)
if(dp[n][i]<ans)ans=dp[n][i];//這裡要是dp[n][i]，因為最後一步也需要轉移
if(ans>=INF)printf("-1\n");
else printf("%d\n",ans);
}
}ac;
int main()
{
int cas=1;
while(scanf("%d",&N)!=EOF,N)
{
ac.clear();
for(int i=0;i<N;i++)
{
scanf("%s",s);
ac.insert(s);
}
ac.getfail();
scanf("%s",str);
printf("Case %d: ",cas++);
ac.solve(str);
}
return 0;
}