正題

題目鏈接:https://www.luogu.com.cn/problem/P4762

---

題目大意

長度為$n$的目標(biāo)串，開始一個空串，可以執(zhí)行以下操作

在頭或者尾加一個字符

復(fù)制一個該串的逆串放在后面

求最少操作次數(shù)。

---

解題思路

我們可以知道答案肯定是一個回文串然后剩下的暴力加上。

我們構(gòu)建一個$PAM$，然后用$f_i$表示帶該回文串需要的最少次數(shù)。

對于一個節(jié)點(diǎn)的轉(zhuǎn)移有$$f_y=min\{f_x+1\}$$
就是該回文串頭尾各加上一個字符。

該回文串還有可能是一個雙倍回文，即一個回文串在復(fù)制一個逆串后回文，那么有我們要像[SHOI2011]雙倍回文這道題目一樣維護(hù)一個最長的不超過該串一半的回文后綴的節(jié)點(diǎn)$hal{f}_i$。

然后有轉(zhuǎn)移
$$f_x=min\{f_{hal{f}_x}+1+\frac{le{n}_x}{2}?le{n}_{hal{f}_x}\}$$

然后答案就是$$min\{n?le{n}_x+f_x\}$$

時間復(fù)雜度$O(4Tn)$

如果用$std$自帶隊(duì)列會比較慢需要自行卡常。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; queue<int> q; const int N=1e5+10; int T,n,m,half[N],f[N],ans; int len[N],fail[N],next[N][4],cnt; char s[N]; int z(char x){if(x=='A') return 0;if(x=='C') return 1;if(x=='G') return 2;if(x=='T') return 3; } int get_fail(int x,int n){while(s[n-len[x]-1]!=s[n])x=fail[x];return x; } void Make_PAM(){int last=0;len[1]=-1;s[0]='#';cnt=fail[0]=1;for(int i=1;i<=n;i++){int val=z(s[i]),x=get_fail(last,i);if(!next[x][val]){len[++cnt]=len[x]+2;int y=get_fail(fail[x],i);fail[cnt]=next[y][val];if(len[cnt]<=2) half[cnt]=fail[cnt];else{int z=half[x];while(s[i-len[z]-1]!=s[i]||((len[z]+2)<<1)>len[cnt])z=fail[z];half[cnt]=next[z][val];}next[x][val]=cnt;}last=next[x][val];}return; } void Solve(){ans=n;for(int i=2;i<=cnt;i++)f[i]=len[i];f[0]=1;q.push(0);while(!q.empty()){int x=q.front();q.pop();f[x]=min(f[x],f[half[x]]+1+len[x]/2-len[half[x]]);ans=min(ans,n-len[x]+f[x]);for(int i=0;i<4;i++){int y=next[x][i];if(!y) continue;f[y]=min(f[y],f[x]+1);q.push(y);}}return; } int main() {scanf("%d",&T);while(T--){for(int i=0;i<=cnt;i++)for(int j=0;j<4;j++)next[i][j]=0;scanf("%s",s+1);n=strlen(s+1);Make_PAM();Solve();printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4762-[CERC2014]Virus synthesis【PAM,dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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