好難啊。。根本不會做。。基本上是抄Claris。。。

題目鏈接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=4044

(luogu)https://www.luogu.org/problemnew/show/P4762

題解: 先觀察到三個(ju)性(fei)質(zhì)(hua): 2操作的結(jié)果一定是一個回文串(廢話), 最后一個2操作之后只能進行1操作(廢話), 只進行1操作花費代價等于字符個數(shù)(廢話)

三句廢話連在一起說: 最后一次2操作產(chǎn)生了一個回文串，此后只能進行1操作，總代價等于回文串代價+目標(biāo)串長度-回文串長度

又因為一個串的本質(zhì)不同回文子串個數(shù)是\(O(n)\)個，而且奇數(shù)長度的回文串沒有任何意義，所以實際上有用的狀態(tài)只是這個串的那些偶數(shù)長度的回文子串。。。

然后就可以在回文自動機上DP

考慮如何生成一個偶數(shù)長度的回文串，最優(yōu)方案最后一步肯定是2操作(廢話)，那么考慮最后2操作之前的一步

因為我們只記錄回文串的狀態(tài)，所以我們希望建立從回文串到回文串的轉(zhuǎn)移，而不能依賴于其他子串。

第一種情況，2操作之前的最后一步將一個字符加在了外面，則代價為該串去掉兩頭字符后的回文串代價+1 (不需要考慮更多，因為回文串去掉兩頭還是回文串)

第二種情況，2操作之前的最后一步將字符加在了里面，于是只能找到該串右半側(cè)的最長回文后綴(或左半側(cè)的最長回文前綴)與之建立聯(lián)系，則代價為(該串串長的一半-右半側(cè)最長回文后綴長度)+右半側(cè)最長回文后綴代價+1 (最后一個+1是指要復(fù)制一次，但是第一種情況的+1指的是在復(fù)制之前加了一個字符，最后一步復(fù)制的代價在去掉兩頭字符的代價中算過了)

要注意初始值是\(f[0]=1\), 因為要求的是長度為0的回文串的代價，相當(dāng)于自我復(fù)制一遍，以供第一種情況轉(zhuǎn)移。

最后的問題是，如何對于一個串的一個回文子串快速求出不超過其長度一半的最長回文后綴？

建回文自動機，在上面進行遞推

一開始覺得是從它的fail遞推下來十分直觀(因為fail本來就是最長回文后綴)，但是實際上這樣并不好(可能需要建出“fail樹”再在上面做一些樹的操作)。

比較好的方法應(yīng)該是對于當(dāng)前要遞推的\(u\)點找到點\(p\)滿足\(son[p][ch]=u\) (\(ch\)是\(u\)的結(jié)束字符，\(p\)點在構(gòu)建回文自動機的過程中已經(jīng)找到了)，然后從\(p\)開始跳fail，直到合法為止，然后再走到它的\(ch\)兒子。因為這樣可以避免在fail樹上自上而下尋找，而采用更方便的\(son\)來向下尋找。

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std;const int N = 1e5+2; const int S = 4; char a[N+3]; int len[N+3]; int fail[N+3]; int son[N+3][S+1]; int bd[N+3]; int dp[N+3]; int que[N+3]; int n,siz,lstpos;int decode(char ch) {if(ch=='A') return 1;else if(ch=='C') return 2;else if(ch=='T') return 3;else if(ch=='G') return 4; }void initPAM() {siz = 1; fail[0] = fail[1] = 1; len[0] = 0; len[1] = -1; lstpos = 1; bd[0] = 0; bd[1] = 1; }void insertchar(int id) { // printf("insert %d\n",a[id]);int p = lstpos;while(a[id-1-len[p]]!=a[id]) {p = fail[p];}if(!son[p][a[id]]){siz++; int u = siz,v = fail[p];while(a[id-1-len[v]]!=a[id]) {v = fail[v];}fail[u] = son[v][a[id]]; len[u] = len[p]+2; son[p][a[id]] = u; // printf("p=%d u=%d\n",p,u);if(len[u]<=2) {bd[u] = fail[u];}else{bd[u] = bd[p];while(a[id-1-len[bd[u]]]!=a[id] || (len[bd[u]]+2)*2>len[u]){bd[u] = fail[bd[u]];}bd[u] = son[bd[u]][a[id]];}}lstpos = son[p][a[id]]; }void clear() {for(int i=0; i<=siz; i++) bd[i] = dp[i] = len[i] = fail[i] = son[i][1] = son[i][2] = son[i][3] = son[i][4] = 0; }int main() {int T; scanf("%d",&T);while(T--){initPAM();scanf("%s",a+1); n = strlen(a+1);for(int i=1; i<=n; i++) a[i] = decode(a[i]);for(int i=1; i<=n; i++){insertchar(i);} // printf("siz=%d\n",siz); // for(int i=0; i<=siz; i++) for(int j=1; j<=S; j++) {if(son[i][j]) printf("son%d %d %d\n",i,j,son[i][j]);} // printf("fail: "); for(int i=0; i<=siz; i++) printf("%d ",fail[i]); puts(""); // printf("bd: "); for(int i=0; i<=siz; i++) printf("%d ",bd[i]); puts("");for(int i=1; i<=siz; i++) {if(len[i]&1) dp[i] = len[i];}int head = 1,tail = 1;que[1] = 0; dp[0] = 1;while(head<=tail){int u = que[head]; head++;for(int i=1; i<=S; i++){if(son[u][i]){tail++; que[tail] = son[u][i];dp[son[u][i]] = min(dp[u]+1,((len[son[u][i]])>>1)-len[bd[son[u][i]]]+dp[bd[son[u][i]]]+1);}}}int ans = n;for(int i=0; i<=siz; i++) ans = min(ans,n-len[i]+dp[i]);printf("%d\n",ans);clear();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ4044 Luogu P4762 [CERC2014]Virus Synthesis (回文自动机、DP)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。