本来想练EX_KMP的，一读题发现是回文串，与回文串有关的一定要用神器manacher啊！！！然后就用manacher写了。。
manacher出所有的回文串半径，然后预处理一遍，最后统计最大值。从左边延续过来的回文串，要看右边有没有构成回文，反之亦然。。。
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 aba 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 acacac
1 6
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=550000;
const int INF=0x3f3f3f3f;
char str[maxn],ans[maxn*2];
int p[maxn*2],table[30],sum[maxn*2];
int pal[maxn*2],par[maxn*2];
void pre()
{
int tot=1;
memset(ans,0,sizeof(ans));
ans[0]=‘$‘;
int len=strlen(str);
for(int i=0;i<len;i++)
{
ans[tot]=‘#‘; tot++;
ans[tot]=str[i]; tot++;
}
ans[tot]=‘#‘;
}
void manacher()
{
pre();
memset(p,0,sizeof(p));
int len=strlen(ans);
int mid=-1,mx=-1;
for(int i=0;i<len;i++)
{
int j=-1;
if(i<mx)
{
j=2*mid-i;
p[i]=min(p[j],mx-i);
}
else p[i]=1;
while(i+p[i]<len&&ans[i+p[i]]==ans[i-p[i]]) p[i]++;
if(p[i]+i>mx)
{
mx=p[i]+i;mid=i;
}
}
}
int main()
{
int T_T;
scanf("%d",&T_T);
while(T_T--)
{
for(int i=0;i<26;i++) scanf("%d",table+i);
scanf("%s",str);
manacher();
sum[0]=0;
int sz=strlen(ans);
for(int i=1;i<sz;i++)
{
sum[i]=sum[i-1];
if(ans[i]>=‘a‘&&ans[i]<=‘z‘)
{
sum[i]+=table[ans[i]-‘a‘];
}
}
ans[1]=‘$‘; ans[sz-1]=‘$‘;
int ret=-INF;
memset(pal,0,sizeof(pal));
memset(par,0,sizeof(par));
for(int i=2;i<sz;i++)
{
int r=p[i]-1;
int L=i-r,R=i+r;
if(ans[L]==‘$‘&&ans[R]==‘$‘) continue;///必须要割两段
if(ans[L]==‘$‘)
{
///后一半可能是回文串，要把结果记录到右端点去
par[R]=sum[R];
if(!(ans[R]>=‘a‘&&ans[R]<=‘z‘)) par[R-1]=sum[R];
else par[R+1]=sum[R];
}
else if(ans[R]==‘$‘)
{
///前一半可能是回文串，要把结果记录到左端点去
int temp=sum[R]-sum[L-1];
pal[L]=temp;
if(!(ans[L]>=‘a‘&&ans[L]<=‘z‘)) pal[L+1]=temp;
else pal[L-1]=temp;
}
}
///统计答案
for(int i=2;i<sz;i++)
{
int r=p[i]-1;
int L=i-r,R=i+r;
if(ans[L]==‘$‘&&ans[R]==‘$‘) continue;///必须要割两段
if(ans[L]==‘$‘)
{
ret=max(ret,sum[R]+pal[R+1]);
}
else if(ans[R]==‘$‘)
{
int temp=sum[R]-sum[L-1];
ret=max(ret,temp+par[L-1]);
}
else ret=max(0,ret); ///当存在负数值的时候0可能是最大的
}
printf("%d\n",ret);
}
return 0;
}
HDOJ 3613 Best Reward,布布扣,bubuko.com
原文：http://blog.csdn.net/u012797220/article/details/22744671