bzoj4044/luoguP4762 [Cerc2014]Virus synthesis(回文自动机+dp)

bzoj Luogu

你要用ATGC四个字母用两种操作拼出给定的串：

1.将其中一个字符放在已有串开头或者结尾。

2.将已有串复制，然后reverse，再接在已有串的头部或者尾部。

一开始已有串为空。求最少操作次数。

len<=100000

题解时间

一个非空串经过一次操作2之后一定是一个偶回文串。

所以考虑建出PAM之后dp。

由于只有偶回文串可以通过操作2产生，所以只有偶回文串参与dp。

对于PAM上一个点 $ x $ :

如果这个串去掉两头一个字母之后的串 $ y $ 非空，那么很明显 $ x $ 可以由 $ y $ 在操作2之前先加上这个字母获得， $ dp[x]=dp[y]+1 $ 。
而如果 $ y $ 为空，那么需要至少两次操作， $ dp[x]=2 $ 。
$ x $ 可以由长度不超过 $ len/2 $ 的后缀回文串延长复制得来，倍增跳fail找到第一个长度不超过 $ len/2 $ 的串 $ y $ ， $ dp[x]=dp[y]+(len[x]/2-len[y])+1 $ 。

#include<bits/stdc++.h>

using namespace std;

namespace RKK

{

const int N=100011;

char str[N];int n;

int cc(char ch)

{

	switch(ch)

	{

		case 'A':return 0;

		case 'G':return 1;

		case 'C':return 2;

		case 'T':return 3;

		default:return 114514;

	}

}

queue<int> q;

struct remilia{int tranc[4],len,fail;void set(){memset(this,0,24);}};

struct sakuya

{

	remilia p[N];

	int size,fin;

	int fa[N][20];

	int dp[N];

	void set()

	{

		p[0].set(),p[1].set();

		p[0].len=0,p[1].len=-1;

		p[0].fail=p[1].fail=1;

		memset(dp,0,(size+1)*sizeof(int));

		size=fin=1;

	}

	sakuya(){size=fin=1;this->set();}

	int match(char *s,int i,int px){return s[i-p[px].len-1]==s[i];}

	void ins(char *s,int i)

	{

		int ch=cc(s[i]);

		int npx,lpx,lpy;

		lpx=fin;

		while(!match(s,i,lpx)) lpx=p[lpx].fail;

		if(!p[lpx].tranc[ch])

		{

			npx=++size;p[npx].set();

			p[npx].len=p[lpx].len+2;

			lpy=p[lpx].fail;

			while(!match(s,i,lpy)) lpy=p[lpy].fail;

			p[npx].fail=p[lpy].tranc[ch];

			p[lpx].tranc[ch]=npx;

		}

		fin=p[lpx].tranc[ch];

	}

	int find(int x)

	{

		int l=p[x].len/2;

		for(int k=19;k>=0;k--)if(p[fa[x][k]].len>l) x=fa[x][k];

		while(p[x].len&1||p[x].len>l) x=fa[x][0];

		return x;

	}

	void work()

	{

		for(int i=0;i<=size;i++) fa[i][0]=p[i].fail;

		for(int k=1;k<20;k++)for(int i=0;i<=size;i++) fa[i][k]=fa[fa[i][k-1]][k-1];

		dp[0]=0;for(int i=0;i<4;i++)if(p[0].tranc[i]) dp[p[0].tranc[i]]=2,q.push(p[0].tranc[i]);

		int ans=n;

		while(!q.empty())

		{

			int x=q.front();q.pop();

			int f=find(x);

			dp[x]=min(dp[x],dp[f]+p[x].len/2-p[f].len+1);

			ans=min(ans,n-p[x].len+dp[x]);

			for(int i=0;i<4;i++)if(p[x].tranc[i]) dp[p[x].tranc[i]]=dp[x]+1,q.push(p[x].tranc[i]);

		}

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

	}

}pam;

int TAT;

int Iris()

{

	scanf("%d",&TAT);

	while(TAT--)

	{

		scanf("%s",str+1),n=strlen(str+1);

		for(int i=1;i<=n;i++) pam.ins(str,i);

		pam.work();

		pam.set();

	}

	return 0;

}

}

int main(){return RKK::Iris();}

巴特西

bzoj4044/luoguP4762 [Cerc2014]Virus synthesis(回文自动机+dp)

bzoj4044/luoguP4762 [Cerc2014]Virus synthesis(回文自动机+dp)

题解时间

最新文章

热门文章