首页 > 代码库 > 吉哥系列故事——完美队形II

吉哥系列故事——完美队形II

2024-07-16 15:23:34   228人阅读

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             else21                 break;22         }23         else24             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\n",ans-1);53    }54   return 0;55 }
View Code

 


联系
我们