bzoj4044 [Cerc2014] Virus synthesis

回文自动机上dp

f[x]表示形成x代表的回文串所需的最小步数，

若len[x]为奇数，f[x]=len[x],因为即使有更优的，也是直接添加，没有复制操作，那样就不用从x转移了。

若len[x]为偶数，f[x]=min(f[fa[x]]+1,len[x]/2-len[fro[x]]+f[fro[x]]+1)，因为fa[x]肯定是最后复制更优，那么将复制前的子串末尾加一个字符即可，fro则是len不大于len[x]/2的最长的x的fail.

memsetT死了，改成每次只memset用的就过了

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define N 100050

 using namespace std;

 int len[N],ch[N][],nxt[N],fro[N],f[N];

 int T,n,ans,last,tot;

 char s[N];

 inline void init(){

     ans=0x7fffffff;

     last=;tot=;

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

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

     nxt[]=nxt[]=;

     len[]=-;

 }

 inline int getfail(int x,int en){

     while(s[en]!=s[en-len[x]-])x=nxt[x];

     return x;

 }

 inline void insert(int t,int en){

     int now=getfail(last,en);

     if(!ch[now][t]){

         int x=++tot;

         memset(ch[x],,sizeof ch[x]);

         len[x]=len[now]+;

         int fa=getfail(nxt[now],en);

         nxt[x]=ch[fa][t];

         fa=fro[now];

         if(len[x]<=)fro[x]=;

         else{

             while(s[en]!=s[en-len[fa]-]||(len[fa]+)*>len[x])

                 fa=nxt[fa];

             fro[x]=ch[fa][t];

         }

         if(len[x]&||len[x]<=)f[x]=len[x];

         else f[x]=min(f[now]+,len[x]/-len[fro[x]]+f[fro[x]]+);

         ans=min(ans,n-len[x]+f[x]);

         ch[now][t]=x;

     }

     last=ch[now][t];

 }

 int hash(char x){

     if(x=='A')return ;

     if(x=='T')return ;

     if(x=='C')return ;

     return ;

 }

 void work(){

     init();

     scanf("%s",s);

     n=strlen(s);

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

         insert(hash(s[i]),i);

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

 }

 int main(){

     scanf("%d",&T);

     while(T--)work();

     return ;

 }

巴特西

bzoj4044 [Cerc2014] Virus synthesis

最新文章

热门文章