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

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

2、走了 i步到達Trie圖上的j結點時，所走過的路徑構成的串與目標串的最 小不匹配字符量。則可以得到轉移方程 dpi sonj = min dpi sonj , dpi-1j+ (tranj sonj != stri ) sonj表示結點j的孩子結點，tranj sonj表示j結點到sonj結點所經過的路徑上的 字母，stri表示目標串的i個字符。代碼：#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不為空，這時我們將p-childt的值賦為q-childt，這樣做 的好處就是在trie圖上走的時候不用考慮失敗指針了。做完這些就可以DP 了。我們定義dpij為構建的字符串長度為i同時到達Trie圖上的j結點時字符串的最大 value值，這時就有dpip= max dpip, dpij+ valuep p 表示 j 的孩子結點，方程不難理解。題目要求出一個字典序最小的串，在DP

8、過程中還得不斷更新這個串。寫了一個很爛的代碼：#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解題報告:自動機+DP。設主串有na個A、nc個C、ng個G、nt個T,于是題意轉化為用na 個A、nc個C、ng個G、nt個T生成一個新串，使模式串匹配次數最大。先將模式串生成自 動機trie圖)，

14、然后在這上面進行DP，狀態(tài)可表示為dpd,s，d為自動機狀態(tài)，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)，總 復雜度 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=