BZOJ 3790 神奇项链（回文自动机+线段树优化DP）

我们预处理出来以i为结尾的最长回文后缀（回文自动机的构建过程中就可以求出）然后就是一个区间覆盖，因为我懒得写贪心，就写了线段树优化的DP。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=101010;

const int INF=1e9;

int L[N],dp[N],q[N],mn[N*5];

char s[N];

struct PAM{

	int len[N],fa[N],size[N],num[N],tot,last,trans[N][27];

	void init(){

		len[0]=0;fa[0]=1;len[1]=-1;fa[1]=0;

		tot=1;last=0;

		memset(trans[1],0,sizeof(trans[1]));

		memset(trans[0],0,sizeof(trans[0]));

	}

	int new_node(int x){

		int now=++tot;

		memset(trans[tot],0,sizeof(trans[tot]));

		len[now]=x;

		return now;

	}

	void ins(int c,int n){

		int u=last;

		while(s[n-len[u]-1]!=s[n])u=fa[u];

		if(trans[u][c]==0){

			int now=new_node(len[u]+2);

			int v=fa[u];

			while(s[n-len[v]-1]!=s[n])v=fa[v];

			fa[now]=trans[v][c];

			trans[u][c]=now;

			num[now]=num[fa[now]]+1;

		}

		last=trans[u][c];size[last]++;

		L[n]=len[last];

	}

}pam;

void build(int l,int r,int now){

	mn[now]=INF;

	if(l==r)return;

	int mid=(l+r)>>1;

	build(l,mid,now<<1);

	build(mid+1,r,now<<1|1);

}

void change(int l,int r,int x,int now){

	if(l==r){mn[now]=dp[l];return;}

	int mid=(l+r)>>1;

	if(x>mid)change(mid+1,r,x,now<<1|1);

	else change(l,mid,x,now<<1);

	mn[now]=min(mn[now<<1],mn[now<<1|1]);

}

int getmin(int l,int r,int L,int R,int now){

	if(l==L&&r==R)return mn[now];

	int mid=(l+r)>>1;

	if(L>mid)return getmin(mid+1,r,L,R,now<<1|1);

	else if(R<=mid)return getmin(l,mid,L,R,now<<1);

	else return min(getmin(l,mid,L,mid,now<<1),getmin(mid+1,r,mid+1,R,now<<1|1));

}

int main(){

	while(scanf("%s",s+1)!=EOF){

		int len=strlen(s+1);

		pam.init();

		for(int i=1;i<=len;i++)pam.ins(s[i]-'a'+1,i);

		build(1,len,1);

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

			if(i-L[i]==0)dp[i]=1;

			else dp[i]=getmin(1,len,i-L[i],i-1,1)+1;

			change(1,len,i,1);

		}

		printf("%d\n",dp[len]-1);

	}

	return 0;

}

巴特西

BZOJ 3790 神奇项链（回文自动机+线段树优化DP）

最新文章

热门文章