题意：

将一段字符串 分割成两个串

如果分割后的串为回文串，则该串的价值为所有字符的权值之和（字符的权值可能为负数），否则为0。

问如何分割，使得两个串权值之和最大

思路：

裸的:

枚举分割点，计算，O（n) 判断是否回文

总复杂度O(n^2)

优化：

利用Manacher的预处理 O（1）判断是否回文

复杂度O(n)

//Manacher/*  ** 求最长回文子串 */ #include 
     
      #include 
      
        #include 
       
        #include 
        
         using namespace std;const int MAXN=550000;char Ma[MAXN*2];int Mp[MAXN*2];void Manacher(char s[],int len){    int l=0;    Ma[l++]='$';    Ma[l++]='#';    for(int i=0;i
         
          i?min(Mp[2*id-i],mx-i):1;        while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++;        if(i+Mp[i]>mx){            mx=i+Mp[i];            id=i;        }     }} /* * abaaba * i:              0 1  2  3  4  5  6  7  8  9 10 11 12 13 *Ma[i]:           $ #  a  #  b  #  a  #  a  # b  #  a  #   *Mp[i]:           1 1  2  1  4  1  2  7  2  1 4  1  2  1 */char s[MAXN];int sum[MAXN*2];int v[30];void input(){    for(int i=1;i<=26;i++)    scanf("%d",&v[i]);    scanf("%s",s);}void get_sum(){    int len=strlen(Ma);    for(int i=1;i
          
           =(i-1)) a1=sum[i]-sum[1]; if(((len+i-1)/2-Mp[(len+i-1)/2]+1)<=(i+1)) a2=sum[len-2]-sum[i]; if(ans
           
            >T; while(T--) { input(); solve(); }}