洛谷P4762 [CERC2014]Virus synthesis（回文自动机+dp）

传送门

回文自动机的好题啊

先建一个回文自动机，然后记$dp[i]$表示转移到$i$节点代表的回文串的最少的需要次数

首先肯定2操作越多越好，经过2操作之后的串必定是一个回文串，所以最后的答案肯定是由一个回文串+不断暴力添加得来，那么答案就是$min(ans,dp[i]+n-len[i])$

然后对于一个串$i$，如果它在前面和后面加上一个字母可以形成回文串$j$，则$dp[j]=dp[i]+1$

为啥嘞？我们可以假设在形成$i$的之前一步把这个字母加上去，执行2操作后就可以变成$j$了

然后我们可以fail指针找到最长的回文串$x$满足$len[x]<=len[i]/2$，那么$dp[i]=min(dp[i],dp[x]+1+len[i]/2-len[x])$（先暴力填好一半，剩下的用2操作）

然后可以用队列记录状态，保证转移至有序的

至于怎么找$x$，我们可以直接在建自动机的时候顺便求出来，就是多跳几次。这个看代码好了

 //minamoto

 #include<cstring>

 #include<cstdio>

 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}

 const int N=2e5+,M=;

 char s[N];int dp[N],len[N],fail[N],ch[N][M];

 int trans[N],last,p,q,str[N],tot,ans,n,qu[N];

 int val[];

 inline int newnode(int x){

     len[++tot]=x;memset(ch[tot],,sizeof(ch[tot])*);return tot;

 }

 inline int getfail(int x,int n){

     while(s[n-len[x]-]!=s[n]) x=fail[x];return x;

 }

 inline void init(){

     val['A']=,val['T']=,val['C']=,val['G']=;

     s[]=-,fail[]=,last=;

     len[]=,len[]=-,tot=;

     memset(ch[],,sizeof(int)*),memset(ch[],,sizeof(int)*);

 }

 void ins(int c,int i){

     p=getfail(last,i);

     if(!ch[p][c]){

         q=newnode(len[p]+);

         fail[q]=ch[getfail(fail[p],i)][c];

         ch[p][c]=q;

         if(len[q]<=) trans[q]=fail[q];

         else{

             int tmp=trans[p];

             while(s[i--len[tmp]]!=s[i]||(len[tmp]+)*>len[q]) tmp=fail[tmp];

             trans[q]=ch[tmp][c];

         }

     }

     last=ch[p][c];

 //    printf("%d\n",last);

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     int T;scanf("%d",&T);

     while(T--){

         scanf("%s",s+);

         init(),ans=n=strlen(s+);

         for(int i=;i<=n;++i) ins(val[s[i]],i);

         for(int i=;i<=tot;++i) dp[i]=len[i];

         int h=,t=;qu[++t]=,dp[]=;

         while(h<=t){

             int u=qu[h++];

             for(int i=;i<;++i){

                 int x=ch[u][i];

                 if(!x) continue;

                 dp[x]=dp[u]+;

                 int y=trans[x];

                 cmin(dp[x],dp[y]++len[x]/-len[y]);

                 cmin(ans,dp[x]+n-len[x]);

                 qu[++t]=x;

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

洛谷P4762 [CERC2014]Virus synthesis（回文自动机+dp）

最新文章

热门文章