首页 > 代码库 > 【POJ3691】DNA repair(AC自动机,DP)

【POJ3691】DNA repair(AC自动机,DP)

题意:

生物课上我们学到,DNA序列中只有A, C, T和G四种片段。

经科学发现,DNA序列中,包含某些片段会产生不好的基因,如片段”ATC”是不好片段,则”AGATCC”, “CATCAA”, “ATCATC”都是不好的DNA序列,这些不好片段我们可以称为病毒片段

现在已知m个病毒片段, 然后给定一个DNA串,问如果使用最少的修改(将DNA中的某个字母,变为其他字母,比如A变T,但变的字母也只能是”ACTG”),使得这个DNA串不包含病毒片段

【数据规模和约定】

 

1<=m<=50  病毒片段长度不超过20,只含A,T,C,G字母

 

DNA串长度不超过1000, 只含A, T, C, G字母

 

思路:AC自动机上的DP

判断是否病毒部分与上一道相同

设dp[i,j]为在原串上前i个字母上改,现在在自动机上j号节点的最小值

\[ dp[i,x]=min\begin{cases} dp[i-1,j] (k=ch[i])\\dp[i-1,j]+1 (k<>ch[i])\end{cases} \]

其中x为j号节点走字母k之后所到达的节点号,要求j号节点为合法节点

答案即为\[ min(dp[len,i]) (i为合法节点) \]

 1 const s:array[1..4]of char=(A,C,G,T);
 2       oo=500000000;
 3 var map:array[1..1100,A..T]of longint;
 4     dp:array[0..1100,0..1000]of longint;
 5     b,f:array[0..1100]of longint;
 6     q:array[1..200000]of longint;
 7     n,tot,i,j,k,d,ans,num,p,cas:longint;
 8     ch:ansistring;
 9 
10 
11 procedure build;
12 var i,d,u:longint;
13 begin
14  u:=1; d:=length(ch);
15  for i:=1 to d do
16  begin
17   if map[u,ch[i]]=0 then begin inc(num); map[u,ch[i]]:=num; end;
18   u:=map[u,ch[i]];
19  end;
20  b[u]:=1;
21 end;
22 
23 procedure acauto;
24 var t,w,u,p,son,i:longint;
25 begin
26  t:=0; w:=1; q[1]:=1;
27  while t<w do
28  begin
29   inc(t); u:=q[t];
30   if b[f[u]]=1 then b[u]:=1;
31   for i:=1 to 4 do
32    if map[u,s[i]]>0 then
33    begin
34     son:=map[u,s[i]];
35     p:=f[u];
36     if u=1 then f[son]:=1
37      else f[son]:=map[p,s[i]];
38     inc(w); q[w]:=son;
39    end
40     else
41     begin
42      p:=f[u];
43      if u=1 then map[u,s[i]]:=1
44       else map[u,s[i]]:=map[p,s[i]];
45     end;
46  end;
47 end;
48 
49 function min(x,y:longint):longint;
50 begin
51  if x<y then exit(x);
52  exit(y);
53 end;
54 
55 begin
56  assign(input,poj3691.in); reset(input);
57  assign(output,poj3691.out); rewrite(output);
58  while not eof do
59  begin
60   fillchar(f,sizeof(f),0);
61   fillchar(b,sizeof(b),0);
62   fillchar(dp,sizeof(dp),$1f);
63   for i:=1 to num do
64    for j:=1 to 4 do map[i,s[j]]:=0;
65   readln(n);
66   if n=0 then break;
67   num:=1; inc(cas);
68   for i:=1 to n do
69   begin
70    readln(ch);
71    build;
72   end;
73   acauto;
74   readln(ch);
75   dp[0,1]:=0; d:=length(ch);
76   for i:=1 to d do
77    for j:=1 to num do
78     if (b[j]=0)and(dp[i-1,j]<oo) then
79      for k:=1 to 4 do
80      begin
81       p:=map[j,s[k]];
82       if b[p]=0 then
83       begin
84        if ch[i]=s[k] then dp[i,p]:=min(dp[i,p],dp[i-1,j])
85         else dp[i,p]:=min(dp[i,p],dp[i-1,j]+1);
86       end;
87      end;
88   ans:=oo;
89   for i:=1 to num do
90    if b[i]=0 then ans:=min(ans,dp[d,i]);
91   write(Case ,cas,: );
92   if ans<oo then writeln(ans)
93    else writeln(-1);
94  end;
95  close(input);
96  close(output);
97 end.

 

 

 

 

【POJ3691】DNA repair(AC自动机,DP)