题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3613
题意就是给你一个串s 然后求把s分成两部分之后的价值总和是多少,分开的串 如果是回文那么价值就是每个字母的价值之和,如果不是那么价值就是0;
例如:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
abbadf
那么可以分成abba 和df abba的价值是1+2+2+1=6,df不是回文串所以价值为0;总价值就是6;
我们可以用数组L【i】R【i】来记录串的前缀长度为i的是否是回文串和后缀长度为i的是否是回文串;
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N = 1e6+; int v[], sum[N], p[N];
///sum[i]代表s串中前i个字符的价值总和;
///p[i]代表以i为中心的回文串的半径(包含i本身);
char s[N];
bool L[N], R[N];
///L[i]表示前i个字符是否是回文串,R[i]表示长度为i的后缀是否为回文串; void Manacher(char s[], int n)
{
int Id = , mx = ;
for(int i=; i<n; i++)
{
if(mx>i)
p[i] = min(mx-i, p[Id*-i]);
else
p[i] = ;
while(s[i+p[i]] == s[i-p[i]])
p[i]++;
if(mx < p[i]+i)
{
mx = p[i]+i;
Id = i;
} if(p[i] == i)
L[p[i]-] = true;
if(p[i]+i == n)
R[p[i]-] = true;
}
} int main()
{
int T;
scanf("%d", &T);
while(T--)
{
memset(L, , sizeof(L));
memset(R, , sizeof(R));
memset(p, , sizeof(p));
memset(sum, , sizeof(sum));
for(int i=; i<; i++)
scanf("%d", &v[i]);
scanf("%s", s);
int len = strlen(s);
for(int i=; i<=len; i++)
sum[i] += sum[i-] + v[s[i-]-'a'];
for(int i=len; i>=; i--)
{
s[i+i+] = s[i];
s[i+i+] = '#';
}
s[]='$';
Manacher(s, *len+);
int ans = ;
for(int i=; i<len; i++)
{
int t=;
if(L[i])
t+=sum[i];
if(R[len-i])
t+=sum[len]-sum[i];
ans = max(ans, t);
}
printf("%d\n", ans);
}
return ;
}