题意：给你一个字符串问切一刀的最大价值。会给出26个字母的价值，而如果你切出来的一个字符串是回文串，则价值为回文串所有字母的和，否则为0.求最大价值。值得注意的是，字母价值可能为负数。
思路：可以想到马拉车算法求出P数组，然后暴力枚举。先预处理出字母价值的前缀和然后再去暴力。暴力过程中还是有很多细节，比如你前和后两个字符串都是回文如何判断，前是回文，后不是回文，前不是回文，后是回文，前后都不是回文。四种情况都要想好确切思路去判断。我是先遍历，找出哪个后缀是回文，然后在去暴力枚举,注意之后操作都在text串中而不是原串。分类讨论一切都在代码中。
#include <iostream> #include <string> #include <cstring> #include <algorithm> #include <cstdio> #include <cctype> #include <queue> #include <stdlib.h> #include <cstdlib> #include <math.h> #include <set> #include"queue" #include <vector> #define inf 107374182 #define M 10010001 #define ll long long #define PII pair<int,int> using namespace std; const int maxn=2000110; char a[maxn],text[maxn]; int P[maxn]; int b[100]; int c[maxn]; int sum[maxn]; void pre_treat(){ int len = strlen(a); for(int i=0;i<len;i++){ text[i*2] = '#'; text[i*2+1] = a[i]; } text[len*2]='#';text[len*2+1]=' '; } void manacher(){ P[0] = 1; //第一个字符的回文串肯定是1 int len = strlen(text); int md = 0; for(int i=1;i<len;i++){ if(i<md+P[md]){ int k = P[md*2-i]; //找到对称点的回文串长度 if(i+k<md+P[md]) P[i] = k; //回文串没有超过右界 else{ k = md+P[md]-i; while(i+k<len&&i+k>=0&&text[i+k]==text[i-k]) k++; md = i; P[i] = k; } } else{ int k = 1; while(i+k<len&&i+k>=0&&text[i+k]==text[i-k]) k++; md = i; P[i] = k; } } // for(int i=0;i<len;i++) printf("%d ",P[i]); //(处理之后的每个点的回文串的长度)/2+1 // printf(" "); } int main() { int t; scanf("%d",&t); while(t--) { for(int i=0;i<26;i++) { scanf("%d",&b[i]); } scanf("%s",a); pre_treat(); int n=strlen(text); for(int i=0;i<=n+1;i++) P[i]=0,c[i]=0; manacher(); sum[0]=0; for(int i=1;i<n;i++) { if(text[i]>='a'&&text[i]<='z') { sum[i]=sum[i-1]+b[text[i]-'a']; } else { sum[i]=sum[i-1]; } } for(int i=n-1;i>=0;i--) { if(i+P[i]-1==n-1) { c[i-P[i]+1]=1; } } int ans=-1000000000; for(int i=1;i<n;i++) { if(c[i]==1) { ans=max(ans,sum[n-1]-sum[i-1]);//前一个不是回文，后面是回文 } if(i-P[i]+1==0&&i+P[i]-1!=n-1) { if(c[i+P[i]-1]==1) { ans=max(ans,sum[n-1]);//都是回文 c[i+P[i]-1]=2; } else { ans=max(ans,sum[i+P[i]-1]);//前一个是回文，后一个不是 } } else { ans=max(0,ans);//都不是回文 } } printf("%d ",ans); } }