hdu 3613马拉车-白红宇

hdu 3613马拉车

阅读量：4204 次

发布时间：2019-05-26

本文共 1075 字，大约阅读时间需要 3 分钟。

////  main.cpp//  马拉车////  Created by liuzhe on 16/11/26.//  Copyright © 2016年 my_code. All rights reserved.//#include
   
      #include
    
       #include
     
        #include
      
         #include
       
          #include
        
          #include
         
           #include
           #include
           
             #define INF 99999999 using namespace std; const int MAX=500000+10; char s[MAX*2]; int p[MAX*2],sum[MAX],val[27];//sum为前i个字符价值和 int per[MAX],pos[MAX];//per标记前i个字符为回文串,pos标记后i个字符为回文串 int main(){ int n; cin>>n; while(n--){ for(int i=0;i<26;++i)scanf("%d",&val[i]); scanf("%s",s); int len=strlen(s),id=0,ans=-INF,temp=0; for(int i=1;i<=len;++i)sum[i]=sum[i-1]+val[s[i-1]-'a']; for(int i=len;i>=0;--i){ s[i+i+2]=s[i]; s[i+i+1]='#'; } s[0]='*'; for(int i=2;i
            
             i)p[i]=min(p[2*id-i],p[id]+id-i); else p[i]=1; while(s[i-p[i]] == s[i+p[i]])++p[i]; if(id+p[id]
             
              ans)ans=temp; temp=0; } cout<
              
               <

题意：上面的数字是26个字母的价值，接下来26个英文字母组成的字符串，将它分成两份，如果分后的串是回文串，则这个串的价值是这个串的所有字母的和，如果不是回文串则这个串价值为0

思路：简单的回文串的变形，先将到每个位置的价值预处理出来然后将字符串跑一边马拉车，我枚举切每个位置的价值和，如现在枚举的是切第三个的位置，则判断一下前三个位置能否形成回文串，那么我们只用判断第二个位置的len1如果等于三则说明是回文串

转载地址：http://eiali.baihongyu.com/

你可能感兴趣的文章