hdu 3613"Best Reward"(Manacher算法)

传送门

题意:

  国王为了犒劳立下战功的大将军Li,决定奖给Li一串项链,这个项链一共包含26中珠子"a~z",每种珠子都有

  相应的价值(-100~100),当某个项链可以构成回文时,那么这个项链的价值就是每个珠子价值的加和,如果

  构不成,那么这个项链的价值就为0;

  求如何将国王奖赏的一串项链拆成价值加和最大的两串项链,求出这个最大价值。

题解:

  本来我是在找有关拓展KMP的相关题目的,百度到一大牛的博客(“扩展KMP题目”),当做到第二个题目的时候,

  思来想去,就是没找到其和拓展KMP的联系,然后,感觉可以用Manacher算法,刷刷刷撸了个Manacher的代码

  提交,AC,所以,我暂且谈谈如何用Manacher算法解这道题;

  ①首先将项链串s[]预处理(了解Manacher算法就理解啥意思了);

  ②准备一个数组sum[],sum[ i ]:预处理后的数组中前 i 个字符对应的价值的加和,'#'当作0;

  ③使用Manacher算法求解出回文半径数组radius[];

  ④假设从 i 位置切割项链,将项链分成[ 0,i ],[ i,len-1 ]两串,分别求解对应的总价值,令ans=max{从i位置分割的总价值}

 AC代码:
 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=5e5+; int val[];
char s[*maxn];
char temp[maxn];
int radius[*maxn];
int sum[*maxn];
void Trans()
{
int len=strlen(s);
strcpy(temp,s);
for(int i=;i < len;++i)
{
s[*i]='#';
s[*i+]=temp[i];
}
s[*len]='#';
s[*len+]='\0';
}
void Manacher()
{
mem(radius,);
int len=strlen(s);
int R=;
int K=;
radius[]=;
for(int i=;i < len;++i)
{
int cnt=;
if(i >= R)
{
while(i+cnt < len && i-cnt >= && s[i+cnt] == s[i-cnt])
cnt++;
radius[i]=cnt;
if(i+cnt- > R)
{
R=i+cnt-;
K=i;
}
}
else
{
int j=K-(i-K);
if(i+radius[j]- != R)
radius[i]=min(R-i+,radius[j]);
else
{
cnt=R-i+;
while(i-cnt >= && i+cnt < len && s[i-cnt] == s[i+cnt])
cnt++;
radius[i]=cnt;
if(i+cnt- > R)
{
R=i+cnt-;
K=i;
}
}
}
}
}
int Solve()
{
Trans();//预处理字符串s
Manacher(); int len=strlen(s);
sum[]=;
for(int i=;i < len;++i)//前缀和
sum[i]=sum[i-]+(s[i] == '#' ? :val[s[i]-'a']); int ans=-INF;
for(int i=;i < len-;i+=)
{
int cnt=;
int x=(i+)>>;//[0,i+1]的中点坐标
if(radius[x] == x+)//判断[0,i]是否构成回文子串
cnt += sum[i]; int y=(len+i)>>;//[i+1,len-1]的中点坐标
if(radius[y] == len-y)//判断[i+1,len-1]是否构成回文子串
cnt += sum[len-]-sum[i];
ans=max(ans,cnt);
}
return ans;
}
int main()
{
// freopen("C:/Users/hyacinthLJP/Desktop/stdin/contest","r",stdin);
int test;
scanf("%d",&test);
while(test--)
{
for(int i=;i < ;++i)
scanf("%d",val+i);
scanf("%s",s);
printf("%d\n",Solve());
}
return ;
}
上一篇:VS 中 无法嵌入互操作类型“……”,请改用适用的接口的解决方法


下一篇:走近深度学习,认识MoXing:初识华为云ModelArts的王牌利器 — MoXing