Problem Description

吉哥又想出了一個新的完美隊形游戲！?
　　假設有n個人按順序站在他的面前，他們的身高分別是h[1], h[2] ... h[n]，吉哥希望從中挑出一些人，讓這些人形成一個新的隊形，新的隊形若滿足以下三點要求，則就是新的完美隊形：?

　　1、挑出的人保持原隊形的相對順序不變，且必須都是在原隊形中連續的；?
　　2、左右對稱，假設有m個人形成新的隊形，則第1個人和第m個人身高相同，第2個人和第m-1個人身高相同，依此類推，當然如果m是奇數，中間那個人可以任意；?
　　3、從左到中間那個人，身高需保證不下降，如果用H表示新隊形的高度，則H[1] <= H[2] <= H[3] .... <= H[mid]。?

　　現在吉哥想知道：最多能選出多少人組成新的完美隊形呢？

Input

輸入數據第一行包含一個整數T，表示總共有T組測試數據(T <= 20)；?
　　每組數據首先是一個整數n(1 <= n <= 100000)，表示原先隊形的人數，接下來一行輸入n個整數，表示原隊形從左到右站的人的身高（50 <= h <= 250，不排除特別矮小和高大的）。

Output

請輸出能組成完美隊形的最多人數，每組輸出占一行。

Sample Input

2
3
51 52 51
4
51 52 52 51

Sample Output

3
4

思路：本質上是求一個最長回文子串，使用馬拉車算法，將 char 數組改為 int 數組，然后將特殊字符 # 改為 0 即可，此外，還要滿足從隊首到最高點滿足最長不下降子串，因此需要特判?newStr[i-p[i]]<=newStr[i-p[i]+2]

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-9 #define INF 0x3f3f3f3f #define LL long long const int MOD=10007; const int N=200000+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std; int str[N]; int newStr[N*2]; int p[N*2]; int n; int init(){newStr[0]=-1;newStr[1]=0;int j=2;int len=n;for (int i=0;i<len;i++){newStr[j++]=str[i];newStr[j++]=0;}return j; }int manacher(){int len=init();int res=-1;int id;int mx=0;for(int i=1;i<len;i++){int j=2*id-i;if(i<mx)p[i]=min(p[j], mx-i);elsep[i]=1;while(newStr[i-p[i]]==newStr[i+p[i]] && newStr[i-p[i]]<=newStr[i-p[i]+2] )p[i]++;if(mx<i+p[i]){id=i;mx=i+p[i];}res=max(res,p[i]-1);}return res; }int main(){int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i<n;++i)scanf("%d",&str[i]);printf("%d\n",manacher());}return 0; }

?

總結

以上是生活随笔為你收集整理的吉哥系列故事――完美队形II（HDU-4513）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。