题目概述

有一个字符串，用若干个回文串覆盖该串，回文串可以重叠，问需要的最少的回文串数 $-1$ 。

解题报告

很容易想到DP $f_i=f_j+1$ 其中以 $i$ 为回文中心的最长回文子串与以 $j$ 为回文中心的最长回文子串相交。

最长回文子串直接Manacher，然后需要考虑DP优化，数据范围小，随便搞搞就行了。

应该也可以不DP直接贪心。

示例程序

可以直接在Manacher串上DP，方便一些。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000;

int n,len,R,pos,p[maxn+5],MIN[(maxn<<2)+5],f[maxn+5];char s[maxn+5],now[maxn+5];

#define Pushup(p) (MIN[p]=min(MIN[(p)<<1],MIN[(p)<<1|1]))
void Insert(int pos,int k,int l=1,int r=n,int p=1){
    if (l==r) {MIN[p]=min(MIN[p],k);return;}int mid=l+(r-l>>1);
    if (pos<=mid) Insert(pos,k,l,mid,p<<1); else Insert(pos,k,mid+1,r,p<<1|1);Pushup(p);
}
int Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l&&r==R) return MIN[p];int mid=l+(r-l>>1);
    if (R<=mid) return Ask(L,R,l,mid,p<<1);if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    return min(Ask(L,mid,l,mid,p<<1),Ask(mid+1,R,mid+1,r,p<<1|1));
}
int main(){
    freopen("necklace.in","r",stdin);freopen("necklace.out","w",stdout);
    while (~scanf("%s",s+1)){
        now[len=1]='%';for (int i=1;s[i];i++) now[++len]=s[i],now[++len]='%';now[len+1]=0;
        for (int i=(R=pos=0,1);i<=len;i++){
            if (i<R) p[i]=min(p[(pos<<1)-i],R-i); else p[i]=1;
            while (1<=i-p[i]&&i+p[i]<=len&&now[i-p[i]]==now[i+p[i]]) p[i]++;
            if (i+p[i]>R) {pos=i;R=i+p[i];}
        }n=len;memset(MIN,63,sizeof(MIN));
        f[1]=0;Insert(1,-1);for (int i=2;i<=n;i++) f[i]=min(Ask(i-p[i]+1,n)+1,i-1),Insert(i+p[i]-1,f[i]);
        int ans=2e9;for (int i=1;i<=n;i++) if (i+p[i]-1==n) ans=min(ans,f[i]);printf("%d\n",ans);
    }return 0;
}