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
2351 52 51451 52 52 51
Sample Output
34
可以说是Manacher的一个应用吧。Manacher在求回文串的过程中非常好。
能够在o(n)的时间内求出最大回文串。
具体详见：点击打开链接
回到本题：求最大回文串的过程中要求中间的不能小于两边。
于是对于Manacher求回文串稍微改动下即可：
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int INF = 0x3f3f3f3f;const int maxn=1e6+100;int str[maxn];int temp[maxn<<1];int Len[maxn<<1];int t,n;int init(){int i,len=n;temp[0]=0;for(int i=1;i<=2*len;i+=2){temp[i]=-1;temp[i+1]=str[i/2];}temp[2*len+1]=-1;temp[2*len+2]=1;return 2*n+1;}int Manacher(){int len=init();int mx=0,ans=0,po=0;//mx:靠右位置,po:i值for(int i=1;i<=len;i++){if(mx>i) Len[i]=min(mx-i,Len[2*po-i]);else Len[i]=1;while(temp[i-Len[i]]==temp[i+Len[i]]){if(Len[i]==1) Len[i]++;else if(temp[i-Len[i]]==-1&&temp[i-Len[i]+1]<=temp[i-Len[i]+3])Len[i]++;else if(temp[i-Len[i]]!=-1&&temp[i-Len[i]]<=temp[i-Len[i]+2])Len[i]++;else break;}if(Len[i]+i>mx){mx=Len[i]+i;po=i;}ans=max(ans,Len[i]);}return ans-1;//Len[i]-1；}int main(){scanf("%d",&t);while(t–){scanf("%d",&n);REP(i,n) scanf("%d",&str[i]);printf("%d\n",Manacher());}return 0;}
快乐要有悲伤作陪，雨过应该就有天晴。
