BZOJ 4044 Virus synthesis (回文自动机+dp)

题目大意：

你可以在一个串的开头或者末尾加入一个字符，或者把当前整个串$reverse$，然后接在前面或者后面，求达到目标串需要的最少操作次数

对目标串建出$PAM$

定义$dp[x]$表示当前在回文树的x节点，拼凑出这个节点表示的回文串所需要的最小操作次数

$fa_{x}$表示沿着树边指向它的父亲，$pre_{x}$表示它的$fail$指针

如果它是奇回文串，一定不能被翻转得到，所以开头结尾各需要加上一个字符，$dp[x]=dp[fa_{x}]+2$

如果它是偶回文串，可以被翻转得到

1.要么是在上次翻转之前先添加一个字符，再翻转得到，$dp[x]=dp[fa_{x}]+1$

2.要么是在这次进行翻转，需要保证被翻转的串长度不大于$dep[x]/2$

可以在回文树上倍增跳$pre$，找到$x$的一个长度不大于$dep[x]/2$的回文后缀所在节点$y$

只需要找后缀的情况即可，其他的情况会被合并到情况一里

剩下的部分也要被暴力地填上，那么$dp[x]=dp[y]+dep[x]/2-dep[y]+1$

 #include <cmath>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 100100

 #define S1 (N1<<1)

 #define ll long long

 #define uint unsigned int

 #define rint register int

 #define dd double

 #define il inline

 #define inf 0x3f3f3f3f

 using namespace std;

 int len,T;

 inline int idx(char x)

 {

     if(x=='A') return ;

     if(x=='C') return ;

     if(x=='G') return ;

     if(x=='T') return ;

 }

 char str[N1];

 int lg[N1];

 namespace PAM{

 int trs[N1][],pre[N1],dep[N1],fa[N1],dp[N1],la,tot;

 int ff[N1][];

 void init()

 {

     tot++;

     memset(trs,,tot**),memset(pre,,tot*);

     memset(ff,,tot**),memset(fa,,tot*);

     memset(dp,,tot*),memset(dep,,tot*);

     la=tot=,dep[]=-;pre[]=pre[]=;

 }

 int chk(char *str,int i,int p){return str[i-dep[p]-]!=str[i]?:;}

 void insert(char *str,int i)

 {

     int p=la,np,fp,c=idx(str[i]);

     while(chk(str,i,p)) p=pre[p];

     if(!trs[p][c])

     {

         np=++tot;

         dep[np]=dep[p]+;

         fp=pre[p];

         while(chk(str,i,fp)) fp=pre[fp];

         pre[np]=trs[fp][c];

         trs[p][c]=np;

         fa[np]=p;

     }

     la=trs[p][c];

 }

 int solve()

 {

     int i,j,x,ans=len,de;

     ff[][]=ff[][]=ff[][]=ff[][]=;

     for(i=;i<=tot;i++) ff[i][]=i,ff[i][]=pre[i];

     for(j=;j<=;j++)

         for(i=;i<=tot;i++)

             ff[i][j]=ff[ ff[i][j-] ][j-];

     dp[]=,dp[]=-;

     for(i=;i<=tot;i++)

     {

         x=i;

         dp[i]=dp[fa[i]]+((dep[i]&)?:);

         if((dep[i]&)) continue;

         for(j=lg[dep[i]];j>=;j--)

             if(dep[ff[x][j]]>=dep[i]/) x=ff[x][j];

         if(dep[x]>dep[i]/) x=pre[x];

         dp[i]=min(dp[i],dp[x]++dep[i]/-dep[x]);

         ans=min(ans,len-dep[i]+dp[i]);

     }

     return ans;

 }

 };

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

         scanf("%s",str+);

         len=strlen(str+);

         int i;

         for(lg[]=,i=;i<=len;i++) lg[i]=lg[i>>]+;

         PAM::init();

         for(i=;i<=len;i++) PAM::insert(str,i);

         printf("%d\n",PAM::solve());

     }

     return ;

 }

巴特西

BZOJ 4044 Virus synthesis (回文自动机+dp)

最新文章

热门文章