【BZOJ-3790】神奇项链 Manacher + 树状数组(奇葩) + DP

时间:2024-09-06 08:37:38

3790: 神奇项链

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 304  Solved: 150
[Submit][Status][Discuss]

Description

母亲节就要到了,小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字母组成的字符串,每个小写字母表示一种颜色。为了制作这个项链,小 H 购买了两个机器。第一个机器可以生成所有形式的回文串,第二个机器可以把两个回文串连接起来,而且第二个机器还有一个特殊的性质:假如一个字符串的后缀和一个字符串的前缀是完全相同的,那么可以将这个重复部分重叠。例如:aba和aca连接起来,可以生成串abaaca或 abaca。现在给出目标项链的样式,询问你需要使用第二个机器多少次才能生成这个特殊的项链。 

Input

输入数据有多行,每行一个字符串,表示目标项链的样式。 

Output

多行,每行一个答案表示最少需要使用第二个机器的次数。 

Sample Input

abcdcba
abacada
abcdef

Sample Output

0
2
5

HINT

每个测试数据,输入不超过 5行 
每行的字符串长度小于等于 50000 

Source

Solution

用来当Manacher模板题..

Manacher算法,一种线性求解最长回文串的算法,简单好写,也好懂,详细见这里:  折越

这道题就是说,转换为多个回文串结合成一个新串,那么对目标串Manacher,对得到的回文串当做一条线段

那么这题转为"线段覆盖"CodeVS上某题,贪心或者DP搞搞就可以了,这里利用树状数组优化一下

这里的树状数组非常神奇,以前只知道树状数组能维护和,没想到可以维护后缀,做法和平常的正好相反

Code

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 50010<<1
int n,len,mx,id,p[maxn],cnt;
char S[maxn>>],s[maxn];
struct TreeNode
{
int a[maxn];
void init() {memset(a,,sizeof(a));}
int lowbit(int x) {return x&(-x);}
int Query(int loc)
{
if (!loc) return ;
int x=0x7fffffff;
for (int i=loc; i<=n; i+=lowbit(i))
x=min(x,a[i]);
return x;
}
void Change(int loc,int D)
{
for (int i=loc; i; i-=lowbit(i))
a[i]=min(a[i],D);
}
}Tree;
void PreWork()
{
cnt=; mx=; id=;
Tree.init(); memset(p,,sizeof(p));
n=strlen(S+); len=n<<|;
s[]='$'; s[]='#'; s[len+]='%';
for (int i=; i<=n; i++)
s[i<<]=S[i],s[i<<|]='#';
}
struct HWCNode
{
int l,r;
bool operator < (const HWCNode & A) const
{return r<A.r;}
}Line[maxn];
void Manacher()
{
PreWork();
for (int i=; i<=len; i++)
{
if (mx>i) p[i]=min(p[id*-i],mx-i);
else p[i]=;
while (s[i-p[i]]==s[p[i]+i]) p[i]++;
int x=(i-p[i])/+,y=(i+p[i])/-;
if (x<=y) Line[++cnt].l=x,Line[cnt].r=y;
if (p[i]+i>mx) mx=p[i]+i,id=i;
}
}
int DP()
{
int ans=0x7fffffff;
sort(Line+,Line+cnt+);
for (int i=; i<=cnt; i++)
{
int D=Tree.Query(Line[i].l-)+;
Tree.Change(Line[i].r,D);
if (Line[i].r==n) ans=min(ans,D);
}
return ans-;
}
int main()
{
while (scanf("%s",S+)!=EOF)
Manacher(),printf("%d\n",DP());
return ;
}