AC自动机上的DP.doc

ADN.cnLibrarySummary动态规划总结by Amber1. Pku 3691 DNA repair 题意为给你一些病毒串，然后给你一个目标串。问你如何修改目标串，使得目标串中不含任何病毒串，且使修改量最少。我们把所有病毒串构成AC自动机，如果 Trie 图中某结点是病毒串的结尾，标记该结点为危险结点。对于某一结点 p，如果他的失败指针所指向的结点为危险结点，则 p 也将标记为危险结点。这时我们沿着AC自动机上走，只要不走过危险结点，最后得到的任何串必然不包含病毒串。这时原问题变为如何在 AC自动机上走(不走过危险结点)，使得走过的路径得到的串与目标串匹配最多，也就是不匹配量最小，修改量最少。我们可以用动态规划解决。用 dpij 表示走了 i 步到达 Trie 图上的 j 结点时，所走过的路径构成的串与目标串的最小不匹配字符量。则可以得到转移方程 dpi sonj = min dpi sonj , dpi-1j+ (tranj sonj != stri ) sonj 表示结点 j 的孩子结点，tranj sonj 表示 j 结点到 sonj 结点所经过的路径上的字母，stri 表示目标串的 i 个字符。代码： PKU 3691 #include#includeintconstN=1010,inf=1000000;#definemin(a,b)(a)(b)?(a):(b)structTrieintfail,flag;intnext4;voidinit()fail=-1;flag=0;for(inti=0;i4;+i)nexti=0;tbN;intidx=0,dpNN,queN,n,m;charstrN;inlineinttoInt(charch)switch(ch)caseA:return0;caseT:return1;caseG:return2;caseC:return3;voidinlineinsert(char*s)intrt=0;while(*s)intt=toInt(*s);if(!tbrt.nextt)tb+idx.init();tbrt.nextt=idx;rt=tbrt.nextt;s+;tbrt.flag=1;voidbfs()inthead=0,tail=0;que0=0;while(head=tail)intnow=quehead+;for(intt=0;t4;+t)if(tbnow.nextt)intp=tbnow.nextt,q=tbnow.fail;while(q!=-1&!tbq.nextt)q=tbq.fail;if(q=-1)tbp.fail=0;elsetbp.fail=tbq.nextt;tbp.flag=tbp.flag|tbtbp.fail.flag;/传遍病毒串que+tail=p;intsolve()m=strlen(str);for(inti=0;i=idx;+i)for(intj=0;j=m;+j)dpji=inf;dp00=0;for(inti=1;i=m;+i)for(intj=0;j=idx;+j)if(dpi-1j!=inf)for(intk=0;k4;+k)intp=tbj.nextk;if(p!=0&!tbp.flag)dpip=min(dpip,dpi-1j+(toInt(stri-1)!=k);elseif(p=0)intf=tbj.fail;while(f!=-1&!tbf.nextk)f=tbf.fail;if(f=-1)p=0;elsep=tbf.nextk;if(!tbp.flag)dpip=min(dpip,dpi-1j+(toInt(stri-1)!=k);intans=inf;for(inti=0;i=idx;+i)ans=min(ans,dpmi);if(ans=inf)return-1;returnans;intmain()inttest=1;while(scanf(%d,&n)!=EOF)if(n=0)return0;tb0.init();idx=0;for(inti=0;ichildt 为空而 q-childt 不为空，这时我们将 p-childt 的值赋为 q-childt，这样做的好处就是在 trie 图上走的时候不用考虑失败指针了。做完这些就可以 DP 了。我们定义 dpij 为构建的字符串长度为 i 同时到达 Trie 图上的 j 结点时字符串的最大 value 值，这时就有 dpip= max dpip, dpij+ valuep p 表示 j 的孩子结点，方程不难理解。题目要求出一个字典序最小的串，在 DP 过程中还得不断更新这个串。写了一个很烂的代码： 代码 #include#include#includeintconstN=5010,M=110;intn,m,hN,cnt,dpMN,pathMN,chMN,queN;intxx,yy,num=0;structTrieintidx,fail;intnext26;voidinit()fail=-1;idx=0;for(inti=0;i26;+i)nexti=0;tbN;charstrM,resM;voidinsert(char*s,intd)intrt=0;while(*s)intt=*s-a;if(!tbrt.nextt)tb+cnt.init();tbrt.nextt=cnt;rt=tbrt.nextt;s+;tbrt.idx=d;voidbfs()inthead=0,tail=0;que0=0;while(head=tail)intnow=quehead+;for(intt=0;t=0)tbnow.nextt=tbq.nextt;voidprint(intx,inty)if(pathxy=-1)return;print(x-1,pathxy);strnum+=chxy+a;intsolve()for(inti=0;i=n;+i)for(intj=0;j=cnt;+j)dpij=-1;pathij=-1;chij=-1;dp00=0;for(inti=1;i=n;+i)for(intj=0;j=cnt;+j)if(dpi-1j!=-1)for(intk=0;k26;+k)if(tbj.nextk)intp=tbj.nextk;if(dpipdpi-1j+htbp.idx)dpip=dpi-1j+htbp.idx;pathip=j;chip=k;elseif(dpip=dpi-1j+htbp.idx)chars1M,s2M;print(i,p);strnum=0;num=0;strcpy(s1,str);intox=pathip,oy=chip;pathip=j,chip=k;print(i,p);strnum=0;num=0;strcpy(s2,str);if(strcmp(s2,s1)0)continue;elsepathip=ox;chip=oy;intans=0;for(inti=1;i=n;+i)for(intj=0;jans)ans=dpij;xx=i,yy=j;intflag=0;for(intj=0;j=cnt;+j)if(dpxxj=ans)num=0;print(xx,j);strnum=0;if(!flag)strcpy(res,str);flag=1;elseif(strcmp(str,res)0)strcpy(res,str);returnans;intmain()inttest;scanf(%d,&test);while(test-)scanf(%d%d,&n,&m);cnt=0;tb0.init();for(inti=1;i=m;+i)scanf(%s,str);insert(str,i);for(inti=1;i=m;+i)scanf(%d,h+i);bfs();intans=solve();if(ans=0)puts();elseputs(res);return0;3. HDU 3341 Losts revenge解题报告:自动机+DP。设主串有na个A、nc个C、ng个G、nt个T，于是题意转化为用na个A、nc个C、ng个G、nt个T生成一个新串，使模式串匹配次数最大。先将模式串生成自动机trie图，然后在这上面进行DP，状态可表示为dpd,s，d为自动机状态，s表示由ma个A、mc个C、mg个G、mt个T的生成串s可表示为ma*(nc+1)*(ng+1)*(nt+1)+mc*(ng+1)*(nt+1)+mg*(nt+1)+mt，转移为O(4)，总复杂度O(500*114*4)。摘自:/vip/Monthly1003/index.php?action=13 代码：代码 #include#include#include#definemax(a,b)(a)(b)?(a):(b)structTrieintflag,fail;intnext4;voidinit()flag=0;fail=-1;for(inti=0;i4;+i)nexti=0;tb600;intn,idx;charstr100;inlineintCh(charch)switch(ch)caseA:return0;caseT:return1;caseG:return2;caseC:return3;voidinsert(char*s)intrt=0;while(*s)intt=Ch(*s);if(tbrt.nextt=0)tb+idx.init();tbrt.nextt=idx;rt=tbrt.nextt;s+;tbrt.flag+;intque20010,head,tail,vis20010;voidbfs()head=0,tail=0,que0=0;while(head=tail)intnow=quehead+;for(intt=0;t4;+t)if(tbnow.nextt)intp=tbnow.nextt,q=tbnow.fail;while(q!=-1&!tbq.nextt)q=tbq.fail;if(q=-1)tbp.fail=0;elsetbp.fail=tbq.nextt;if(tbtbp.fail.flag)tbp.flag+=tbtbp.fail.flag;que+tail=p;elseintq=tbnow.fail;while(q!=-1&!tbq.nextt)q=tbq.fail;if(q!=-1)tbnow.nextt=tbq.nextt;intdp20000510,num4,base4;charSS4=A,T,G,C;voidinlineget_num(intstate,intatgc4)for(inti=0;i4;+i)atgci=state/basei;state%=basei;intinlinenew_state(intatgc4,intk)intres=0;for(inti=0;i4;+i)if(i!=k)res+=basei*atgci;elseres+=basei*(atgci+1);returnres;intsolve()intlen=strlen(str);for(inti=0;i4;+i)numi=0;for(inti=0;ilen;+i)numCh(stri)+;inttot=0;for(inti=0;i4;+i)intt=1;for(intj=i+1;j4;+j)t*=(numj+1);basei=t;tot+=basei*numi;inthead=0,tail=0,size=1;for(inti=0;i=tot;+i)for(intj=0;j=idx;+j)dpij=-1;for(inti=0;i=tot;+i)visi=0;vis0=1;que0=0;dp00=0;while(head=tail)intts=0;for(inti=0;isize;+i)intstate=quehead+,atgc4;visstate=0;if(state=tot)continue;get_num(state,atgc);for(intp=0;p=idx;+p)if(dpstatep!=-1)for(intk=0;k4;+k)if(atgck+1dpnewStateq)dpnewStateq=dpstatep+tbq.flag;if(!visnewState)que+tail=newState;ts+;