BZOJ3790 神奇项链

2014.12.16 13:31 Tue| 3 visits oi_2015| 2015_刷题日常| Text

就是为了这一道题,我特意学习了Manacher算法……

颓了两天,玩了玩Ubuntu,恰好小伙伴们准备会考,,

祝他们会考愉快 →_→

Solution

题意即给出字符串,求它至少可以由多少可重叠的回文串组成。

首先可以使用Manacher算法求出所有极长回文子序列,算出它们各自可以覆盖的区间。对于每一个位置,记录以其为终点的子序列起点最长能延伸到的位置。在此基础上直接使用树状数组优化DP即可。

就这么一道破题拖了好久……真是的……

Code

#include <bits/stdc++.h>
using namespace std;
#define N 50005
#define inf 0x3f3f3f3f

char s[N*2],str[N];
int n,p[N*2],ans[N*2],f[N],fenwick[N];

int manacher(char str[],int len)
{
    s[0]='$'; s[1]='#';
    for(int i=0;i<len;i++)
        s[i*2+2]=str[i], s[i*2+3]='#';
    len=len*2+2;
    int id=0,maxp=0,re=0;
    for(int i=1;i<=len;i++)
    {
        if(maxp>i) p[i]=min(p[id*2-i],maxp-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) p[i]++;
        if(i+p[i]>maxp) maxp=i+p[i], id=i;
        re=max(re,p[i]);
    }
    return re-1;
}

void modify(int x,int y)
{
    for(int i=x;i;i-=i&-i)
        fenwick[i]=min(fenwick[i],y);
}

int query(int x)
{
    int re=fenwick[x];
    for(int i=x;x&&i<=n;i+=i&-i)
        re=min(re,fenwick[i]);
    return re;
}

int main()
{
    while(scanf("%s",str)!=EOF)
    {
        memset(p,0,sizeof p);
        memset(s,0,sizeof s);
        memset(fenwick,0x3f,sizeof fenwick);
        n=strlen(str);
        manacher(str,n);
        for(int i=1;i<=n*2+2;i++) f[i]=i;
        for(int i=2;i<=n*2+2;i++)
            f[(i+p[i]-2)/2]=min(f[(i+p[i]-2)/2],(i-p[i]+2)/2);
        fenwick[0]=0;
        for(int i=1;i<=n;i++) ans[i]=query(f[i]-1)+1,modify(i,ans[i]);
        cout<<ans[n]-1<<endl;
    }
    return 0;
}