bzoj 3790: 神奇项链 （manacher+线段树优化DP）

题目描述

传送门

题目大意： 有两个机器，第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。现在给出目标项链的样式，询问你需要使用第二个机器多少次才能生成这个特殊的项链。

题解

manacher，然后转换成用最少的线段覆盖整个区间，变成Dp问题再进行优化

代码

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define N 500003 using namespace std; int t[N],a[N],f[N],tr[N],n; char s[N]; void manacher() { int mx=0,id=0; for (int i=1;i<=n;i++) { if (mx>=i) t[i]=min(t[2*id-i],mx-i); else t[i]=0; for (;i-t[i]-1>=0&&i+t[i]+1<=n&&a[i-t[i]-1]==a[i+t[i]+1];t[i]++); if (t[i]+i>=mx) id=i,mx=t[i]+i; } } void update(int now) { tr[now]=min(tr[now<<1],tr[now<<1|1]); } void pointchange(int now,int l,int r,int x,int val) { if (l==r) { tr[now]=min(tr[now],val); return; } int mid=(l+r)/2; if (x<=mid) pointchange(now<<1,l,mid,x,val); else pointchange(now<<1|1,mid+1,r,x,val); update(now); } int query(int now,int l,int r,int ll,int rr) { if (ll<=0||rr<ll) return 0; if (ll<=l&&r<=rr) return tr[now]; int mid=(l+r)/2; int ans=1000000000; if (ll<=mid) ans=min(ans,query(now<<1,l,mid,ll,rr)); if (rr>mid) ans=min(ans,query(now<<1|1,mid+1,r,ll,rr)); return ans; } int main() { freopen("a.in","r",stdin); while (scanf("%s",s+1)!=EOF) { n=strlen(s+1); a[1]=0; for (int i=1;i<=n;i++) { a[2*i]=s[i]-'a'+1; a[2*i+1]=0; } n=2*n+1; manacher(); memset(tr,127,sizeof(tr)); for (int i=1;i<=n;i++){ f[i]=query(1,1,n,i-t[i]-1,i+t[i])+1; pointchange(1,1,n,i+t[i]-1,f[i]); } int ans=n; for (int i=1;i<=n;i++) if (i+t[i]-1>=n-1) ans=min(ans,f[i]); printf("%d\n",ans-1); } }