在AC自動(dòng)機(jī)上動(dòng)態(tài)規(guī)劃

1、在AC自動(dòng)機(jī)上動(dòng)態(tài)規(guī)劃1. Pku 3691 DNA repair題意為給你一些病毒串，然后給你一個(gè)目標(biāo)串。問(wèn)你如何修改目標(biāo)串，使得目標(biāo)串中不 含任何病毒串，且使修改量最少。我們把所有病毒串構(gòu)成AC自動(dòng)機(jī)，如果Trie圖中某結(jié)點(diǎn)是病毒串的結(jié)尾，標(biāo)記該結(jié)點(diǎn)為危 險(xiǎn)結(jié)點(diǎn)。對(duì)于某一結(jié)點(diǎn)p，如果他的失敗指針?biāo)赶虻慕Y(jié)點(diǎn)為危險(xiǎn)結(jié)點(diǎn)，則p也將標(biāo)記為危 險(xiǎn)結(jié)點(diǎn)。這時(shí)我們沿著AC自動(dòng)機(jī)上走，只要不走過(guò)危險(xiǎn)結(jié)點(diǎn)，最后得到的任何串必然不包 含病毒串。這時(shí)原問(wèn)題變?yōu)槿绾卧贏C自動(dòng)機(jī)上走(不走過(guò)危險(xiǎn)結(jié)點(diǎn))，使得走過(guò)的路徑得到 的串與目標(biāo)串匹配最多，也就是不匹配量最小，修改量最少。我們可以用動(dòng)態(tài)規(guī)劃解決。用dpij表示

2、走了 i步到達(dá)Trie圖上的j結(jié)點(diǎn)時(shí)，所走過(guò)的路徑構(gòu)成的串與目標(biāo)串的最 小不匹配字符量。則可以得到轉(zhuǎn)移方程 dpi sonj = min dpi sonj , dpi-1j+ (tranj sonj != stri ) sonj表示結(jié)點(diǎn)j的孩子結(jié)點(diǎn)，tranj sonj表示j結(jié)點(diǎn)到sonj結(jié)點(diǎn)所經(jīng)過(guò)的路徑上的 字母，stri表示目標(biāo)串的i個(gè)字符。代碼：#include #include int const N= 1010, inf= 1000000;#define min(a,b) (a)(b)?(a):(b)struct Trieint fail, flag;int next4;void i

3、nit()fail= -1; flag= 0;for( int i= 0; i 4; +i) nexti= 0;tbN;int idx= 0, dpNN, queN, n, m;char strN;inline int toInt( char ch )(switch( ch)(case A: return 0;case T: return 1;case G: return 2;case C: return 3;void inline insert( char* s )(int rt= 0;while( *s )(int t= toInt( *s );if( !tbrt.nextt)(tb+id

4、x.init();tbrt.nextt= idx;rt= tbrt.nextt; s+;tbrt.flag= 1;void bfs()(int head= 0, tail= 0; que0= 0;while( head= tail)(int now= quehead+;for( int t= 0; t 4; +t) if( tbnow.nextt)(int p= tbnow. nextt, q= tb now.fail;while( -1 & !tbq.nextt) q= tbq.fail;if( q= -1) tbp.fail= 0;else (tbp.fail= tbq.nextt;tbp

5、.flag= tb p.flag| tb tbp.fail .flag;/傳遍病毒串que+tail= p;int solve()(m= strlen( str );for( int i= 0; i= idx; +i)for( int j= 0; j= m; +j) dpji= inf;dp00= 0;for( int i= 1; i= m; +i)(for( int j= 0; j= idx; +j)if( dpi-1j!= inf)(for( int k= 0; k 4; +k)(int p= tbj.nextk;if( 0 & !tbp.flag )dpip= min( dpip, dp

6、i-1j+ ( toInt( stri-1 )!= k);else if( p= 0 )(int f= tbj.fail;while( -1 & !tbf.nextk) f= tbf.fail;if(f=-1) p= 0;else p= tbf.nextk;if( !tbp.flag)dpip= min( dpip, dpi-1j+ ( toInt( stri-1 )!= k );int ans= inf;for( int i= 0; i= idx; +i)ans= min( ans, dpmi);if( ans= inf) return -1;return ans;int main()(in

7、t test= 1;while( scanf(%d”,&n)!= EOF)(if( n= 0 ) return 0;tb0.ini(); idx= 0;for( int i= 0; ichildt為空而q-childt不為空，這時(shí)我們將p-childt的值賦為q-childt，這樣做 的好處就是在trie圖上走的時(shí)候不用考慮失敗指針了。做完這些就可以DP 了。我們定義dpij為構(gòu)建的字符串長(zhǎng)度為i同時(shí)到達(dá)Trie圖上的j結(jié)點(diǎn)時(shí)字符串的最大 value值，這時(shí)就有dpip= max dpip, dpij+ valuep p 表示 j 的孩子結(jié)點(diǎn)，方程不難理解。題目要求出一個(gè)字典序最小的串，在DP

8、過(guò)程中還得不斷更新這個(gè)串。寫了一個(gè)很爛的代碼：#include #include #include int const N= 5010, M= 110;int n, m, hN, cnt, dpMN, pathMN, chMN, queN;int xx, yy, num= 0;struct Trieint idx, fail;int next26;void init()fail= -1; idx= 0;for( int i= 0; i 26; +i) nexti= 0;char strM, resM;void insert( char* s, int d )(int rt= 0;while(

9、*s )(int t= *s- a;if( !tbrt.nextt)(tb+cnt.init();tbrt.nextt= cnt;rt= tbrt.nextt; s+;tbrt.idx= d;void bfs()(int head= 0, tail= 0; que0= 0;while( head= tail)(int now= quehead+;for( int t= 0; t= 0 ) tbnow.nextt= tbq.nextt;void print( int x, int y )(if( pathxy= -1 ) return;print( x- 1, pathxy);strnum+=

10、chxy+ a;int solve()(for( int i= 0; i= n; +i)for( int j= 0; j= cnt; +j) (dpij= -1; pathij= -1; chij= -1; dp00= 0;for( int i= 1; i= n; +i)(for( int j= 0; j= cnt; +j)if( dpi-1j!=-1)for( int k= 0; k 26; +k)if( tbj.nextk)int p= tbj.nextk;if( dpip dpi-1j+ h tbp.idx)dpip= dpi-1j+ h tbp.idx ;pathip=j; chip=

11、 k;elseif( dpip= dpi-1j+ h tbp.idx)char s1M, s2M;print( i, p ); strnum= 0; num= 0; strcpy( s1, str );int ox= pathip, oy= chip;pathip=j, chip= k;print( i, p ); strnum= 0; num= 0; strcpy( s2, str );if( strcmp( s2, s1 ) 0 ) continue;else pathip= ox; chip= oy;int ans= 0;for( int i= 1; i= n; +i)for( int

12、j= 0; j ans )ans= dpij; xx= i, yy= j;int flag= 0;for( int j= 0; j= cnt; +j)if( dpxxj= ans)(num= 0; print(xx,j); strnum= 0;if( !flag)(strcpy( res, str);flag= 1;else if( strcmp( str, res ) 0 )( strcpy( res, str);return ans;int main()(int test;scanf(%d”,&test);while( test-)(scanf(%d%d”,&n,&m);cnt= 0; t

13、b0.ini ();for( int i= 1; i= m; +i)( scanf(%s,str);insert(str, i); for( int i= 1; i= m; +i) scanf(%d”, h+ i);bfs();int ans= solve();if( ans= 0 ) puts();else puts(res);return 0;3. HDU 3341 Losts revenge解題報(bào)告:自動(dòng)機(jī)+DP。設(shè)主串有na個(gè)A、nc個(gè)C、ng個(gè)G、nt個(gè)T,于是題意轉(zhuǎn)化為用na 個(gè)A、nc個(gè)C、ng個(gè)G、nt個(gè)T生成一個(gè)新串，使模式串匹配次數(shù)最大。先將模式串生成自 動(dòng)機(jī)trie圖)，

14、然后在這上面進(jìn)行DP，狀態(tài)可表示為dpd,s，d為自動(dòng)機(jī)狀態(tài)，s表示由ma 個(gè) A、mc 個(gè) C、mg 個(gè) G、mt 個(gè)T 的生成串s 可表示為 ma*(nc+1)*(ng+1)*(nt+1)+mc*(ng+1)*(nt+1)+mg*(nt+1)+mt )，轉(zhuǎn)移為 O(4)，總 復(fù)雜度 0(500*11人4*4)。摘自: HYPERLINK /vip/Monthly1003/index.php2actionT3 /vip/Monthly1003/index.php2actionT3代碼：#include #include #include #define max(a,b) (a) (b)? (

15、a): (b)struct Trie(int flag, fail;int next4;void init()(flag= 0; fai= -1;for( int i= 0; i4 ; +i) nexti= 0;tb600;int n, idx;char str100;inline int Ch( char ch )(switch( ch)(case A: return 0;case T: return 1;case G: return 2;case C: return 3;void insert( char* s )(int rt= 0;while( *s )(int t= Ch(*s);i

16、f( tbrt.nextt= 0)(tb+idx.init();tbrt.nextt= idx;rt= tbrt.nextt; s+;tbrt.flag+;int que20010, head, tail, vis20010;void bfs()(head= 0, tail= 0, que0= 0;while( head= tail)(int now= quehead+;for( int t= 0; t 4; +t)if( tbnow.nextt)(int p= tbnow. nextt, q= tb now.fail;while( -1 & !tbq.nextt) q= tbq.fail;i

17、f( q= -1) tbp.fail= 0;else(tbp.fail= tbq.nextt;if( tb tbp.fail.flag ) tbp.flag+= tb tbp.fail.flag;que+tail= p;else(int q= tbnow.fail;while( -1 & !tbq.nextt) q= tbq.fail;if( -1 ) tbnow.nextt= tbq.nextt;int dp20000510, num4, base 4;char SS4= A, T, G, C ;void inline get_num( int state, int atgc4)for( i

18、nt i= 0; i 4; +i)atgci= state/ basei;state%= basei;int inline new_state(int atgc4, int k)(int res= 0;for( int i= 0; i 4; +i)if( k) res+= basei* atgci;else res+= basei* ( atgci+ 1 );return res;int solve()(int len= strlen(str);for( int i= 0; i 4; +i) numi= 0;for( int i= 0; i len; +i) num Ch(stri) +;int tot= 0;for( int i= 0; i 4; +i)(intt= 1;for( int j= i+ 1; j 4; +j) t*= ( numj+ 1 );basei= t; tot+= basei* numi;int head= 0, tail= 0, size= 1;for( int i= 0; i= tot; +i)for( int j= 0; j= idx; +j) dpij= -1;for( int i= 0; i= tot; +i) visi= 0; vis0= 1;que0=