hdu4513:http://acm.hdu.edu.cn/showproblem.php?pid=4513
题意：给以一个序列，然后让你求一个最长回文序列的长度，这个序列的从左到最中间那个数是不降的，从中间那里向右边的话是不增的。
题解：用Manacher搞定，直接套模板还不行，还要做一些判断。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define M 800050 6 using namespace std; 7 int str1[M],str[M*2]; 8 int rad[M]; 9 void Manacher(int *rad, int *str,int n){ 10 int i,mx=0,id; 11 for(int i=1;i<n;i++){//下标从1开始 12 if(mx>i){ 13 rad[i]=min(rad[2*id-i],mx-i); 14 } 15 else rad[i]=1; 16 while(str[i+rad[i]]==str[i-rad[i]]){ 17 if(str[i+rad[i]]!=40){ 18 if(str[i+rad[i]]<=str[i+rad[i]-2]) 19 rad[i]++; 20 else 21 break; 22 } 23 else 24 rad[i]++; 25 } 26 if(rad[i]+i>mx){ 27 mx=rad[i]+i; 28 id=i; 29 } 30 } 31 } 32 int main(){ 33 int ans,cas; 34 scanf("%d",&cas); 35 while(cas--){ 36 int nn; 37 scanf("%d",&nn); 38 for(int i=0;i<nn;i++) 39 scanf("%d",&str1[i]); 40 memset(str,0,sizeof(str)); 41 int n=nn*2+2; 42 str[0]=40; 43 memset(rad,0,sizeof(rad)); 44 for(int i=0;i<=nn;i++){ 45 str[2*i+1]=40; 46 str[2*i+2]=str1[i]; 47 } 48 Manacher(rad,str,n); 49 ans=1; 50 for(int i=0;i<n;i++) 51 ans=max(ans,rad[i]); 52 printf("%d ",ans-1); 53 } 54 return 0; 55 }