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

时间:2023-02-01 17:23:49

题意:

生物课上我们学到,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为合法节点) \]

 const s:array[..]of char=('A','C','G','T');
oo=;
var map:array[..,'A'..'T']of longint;
dp:array[..,..]of longint;
b,f:array[..]of longint;
q:array[..]of longint;
n,tot,i,j,k,d,ans,num,p,cas:longint;
ch:ansistring; procedure build;
var i,d,u:longint;
begin
u:=; d:=length(ch);
for i:= to d do
begin
if map[u,ch[i]]= then begin inc(num); map[u,ch[i]]:=num; end;
u:=map[u,ch[i]];
end;
b[u]:=;
end; procedure acauto;
var t,w,u,p,son,i:longint;
begin
t:=; w:=; q[]:=;
while t<w do
begin
inc(t); u:=q[t];
if b[f[u]]= then b[u]:=;
for i:= to do
if map[u,s[i]]> then
begin
son:=map[u,s[i]];
p:=f[u];
if u= then f[son]:=
else f[son]:=map[p,s[i]];
inc(w); q[w]:=son;
end
else
begin
p:=f[u];
if u= then map[u,s[i]]:=
else map[u,s[i]]:=map[p,s[i]];
end;
end;
end; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; begin
assign(input,'poj3691.in'); reset(input);
assign(output,'poj3691.out'); rewrite(output);
while not eof do
begin
fillchar(f,sizeof(f),);
fillchar(b,sizeof(b),);
fillchar(dp,sizeof(dp),$1f);
for i:= to num do
for j:= to do map[i,s[j]]:=;
readln(n);
if n= then break;
num:=; inc(cas);
for i:= to n do
begin
readln(ch);
build;
end;
acauto;
readln(ch);
dp[,]:=; d:=length(ch);
for i:= to d do
for j:= to num do
if (b[j]=)and(dp[i-,j]<oo) then
for k:= to do
begin
p:=map[j,s[k]];
if b[p]= then
begin
if ch[i]=s[k] then dp[i,p]:=min(dp[i,p],dp[i-,j])
else dp[i,p]:=min(dp[i,p],dp[i-,j]+);
end;
end;
ans:=oo;
for i:= to num do
if b[i]= then ans:=min(ans,dp[d,i]);
write('Case ',cas,': ');
if ans<oo then writeln(ans)
else writeln(-);
end;
close(input);
close(output);
end.