HDU - 3613 - Best Reward（马拉车加暴力）

博主链接

题目链接

题意：

字母表的26个字母都有一个价值，给你一个字符串，将该字符串切成两份，对于每一份，如果是回文串，就获得该子串的字母价值之和，否则该子串的价值为0。求出将字符串切成两份后能够获得的最大价值。

题解：

先用Manacher算法求出以每个字母为中心的回文串的长度，并计算该字符串的前缀价值和。然后枚举切割点，得到两份子串。这样就可以知道每个子串的中心点，然后检查以该子串的中心点作为中心点的回文串的长度，如果长度等于该子串的长度，那么就加上该子串的价值。然后和最优价值比较就行了。

#include<stdio.h>
#include<bits/stdc++.h>
#define met(a) memset(a,0,sizeof(a));
using namespace std;
typedef long long ll;
const int maxn = 500050;
char s[maxn];
char s_new[maxn * 2];
int p[maxn * 2];
int sum[maxn];
int Init(){
	int len = strlen(s);
	s_new[0] = '$';
	s_new[1] = '#';
	int j = 2;
	for (int i = 0; i < len; i++){
		s_new[j++] = s[i];
		s_new[j++] = '#';
	}
	s_new[j] = '\0';
	//printf("%s\n",s_new);
	return j;  //返回s_new的长度  
}
void Manacher(){
	int len = Init();  //取得新字符串长度并完成向s_new的转换  
	//int maxLen = -1;   //最长回文长度  
	int id;
	int mx = 0;
	for (int i = 1; i < len; i++){
		if (i < mx)
			p[i] = min(p[2 * id - i], mx - i);  //需搞清楚上面那张图含义, mx和2*id-i的含义
		else
			p[i] = 1;
		while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断，因为左有'$',右有'\0'  
			p[i]++;
		//我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率 
		if (mx < i + p[i])  {
			id = i;
			mx = i + p[i];
		}
		//maxLen = max(maxLen, p[i] - 1);
		// printf("%d %d %d\n",mx,id,maxLen);
	}
	/*for(int i=1;i<=len;i++)printf("%d ",p[i]);
	printf("\n");*/
	return ;
}
int v[30];
int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		memset(p, 0, sizeof(p));
		for (int i = 0; i < 26; i++)scanf("%d", &v[i]);
		scanf("%s", s);
		sum[0] = v[s[0] - 'a'];
		for (int i = 1; s[i]; i++){
			sum[i] = sum[i - 1] + v[s[i] - 'a'];
		}
		Manacher();
		int Mx = 0;
		int len = strlen(s);
		for (int i = 0; i < len - 1; i++){
			int tmp = 0;
			int num = p[i + 2] - 1;
			if (num == i + 1)tmp += sum[i];
			num = p[i + len + 2] - 1;
			if (num == len - i - 1)tmp += sum[len - 1] - sum[i];
			if (tmp>Mx)Mx = tmp;
		}
		printf("%d\n", Mx);
	}
	return 0;
}