BZOJ3790: 神奇项链 Manacher+线段树优化dp

首先令\(f_i\)表示前\(i\)个字符最少能被拆分为几个回文串，很显然能够列出转移方程:

\[f_{i}=min\{f_{j}+1\}(i-len[i]\leq{j}<i)\]

其中\(len[i]\)表示以位置\(i\)为结尾的最长回文串长度。

于是我们可以利用Manacher算法或者hash预处理出\(len\)数组，随后用线段树优化dp即可。时间复杂度\(O(nlogn)\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
 
#define INF 1<<30
 
#define N 50010
char s[N],work[N<<1];
 
struct SegmentTree{
    int Min[262144],M;
    inline void Init(int _siz){
        for(M=1;M<(_siz+2);M<<=1);
        memset(Min,0x3f,sizeof Min);
    }
    inline void Modify(int ins,int _v){
        for(Min[ins+=M]=_v,ins>>=1;ins;ins>>=1)Min[ins]=std::min(Min[ins<<1],Min[ins<<1^1]);
    }
    inline int Query(int tl,int tr){
        int res=INF;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if(~tl&1)res=std::min(res,Min[tl^1]);
            if(tr&1)res=std::min(res,Min[tr^1]);
        }return res;
    }
}Seg;
 
int left[N],p[N<<1],f[N],g[N];
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    register int i,j;
    while(scanf("%s",s+1)!=EOF){
        int len=strlen(s+1);
 
        for(i=1;i<=len;++i){
            work[2*i-1]=s[i];
            work[2*i]='$';
        }work[len*=2]='@';
 
        memset(p,0,sizeof p);
        int ins(0),Maxid(0);
        for(i=1;i<=len;++i){
            if(Maxid>i)p[i]=std::min(p[2*ins-i],Maxid-i+1);
            while(work[i+p[i]]==work[i-p[i]])++p[i];
            if(i+p[i]-1>Maxid){
                for(j=Maxid+1;j<=i+p[i]-1;++j)left[j]=i;
                Maxid=i+p[i]-1,ins=i;
            } 
        }
 
        for(i=1;i<=len;++i)if(i&1)f[(i>>1)+1]=i-left[i]+1;
 
        Seg.Init(len/=2);
         
        for(i=1;i<=len;++i){
            if(i==f[i])g[i]=1;
            else g[i]=Seg.Query(i-f[i],i-1)+1;
            Seg.Modify(i,g[i]);
        }
 
        printf("%d\n",g[len]-1);
    }
 
    return 0;
}