【BZOJ】3790 神奇项链

【算法】(manacher+贪心)||(manacher+DP+树状数组/线段树)

【题解】

manacher求回文串，后得到线段，做一点计算映射回原串线段。

然后问题转化为可重叠区间线段覆盖问题，可以贪心解决。

排序左端点，同一左端点取最长段，然后在此段中找到右端点最靠右的线段，线性更新并累加。

DP的话：f[i]表示刚好覆盖1...i的最少线段(即最后一条线段右端点在i上)，则按顺序枚举线段a[i]，

f[a[i].r]=min(f[j])+1 , j=(a[i].l,a[i].l+1,...,a[i].r-1)，显然a[n]为答案。

于是可以用树状数组或线段树来在线维护min(f[j])。

两者复杂度皆为o(n log n)。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=;

int n,p[maxn];

char s[maxn],ss[maxn];

struct cyc{int l,r;}a[maxn];

bool cmp(cyc a,cyc b)

{return a.l<b.l||(a.l==b.l&&a.r>b.r);}

void manacher()

{

    memset(p,,*(n+));

    int id=,mx=;

    for(int i=;i<=n;i++)

     {

         if(mx>i)

          p[i]=min(p[id*-],mx-i+);

         else p[i]=;

         while(s[i+p[i]]==s[i-p[i]])p[i]++;

         if(i+p[i]->mx)

          {

              mx=i+p[i]-;

              id=i;

          }

//         printf("p[%d]=%d\n",i,p[i]);

         if(i%)a[i].l=i/-p[i]/+,a[i].r=i/+p[i]/;

          else a[i].l=i/-p[i]/+,a[i].r=i/+p[i]/-;

         if(a[i].l>a[i].r)a[i].l=a[i].r=;

     }

//    for(int i=1;i<=n;i++)printf("%d %d\n",a[i].l,a[i].r);

}

int main()

{

    while(scanf("%s",ss+)==)

     {

         int tot=strlen(ss+);

         n=;s[]='$';s[]='#';

         for(int i=;i<=tot;i++)s[++n]=ss[i],s[++n]='#';

         manacher();

         sort(a+,a+n+,cmp);

         int right=a[].r,ans=,mx=;

//         for(int i=1;i<=n;i++)printf("a[%d]l=%d r=%d\n",i,a[i].l,a[i].r);

         for(int i=;i<=n;i++)

         if(a[i].l!=a[i-].l)

           {

               if(a[i].l>right+)ans++,right=mx;

               mx=max(mx,a[i].r);

           }

         if(right<tot)ans++;

         printf("%d\n",ans-);

     }

    return ;

}

贪心