分析：该題可以通过求最长回文串的方法来解决；求最长回文串使用manacher算法，O(n)时间复杂度。注意：while(a[i-len[i]]==a[i+len[i]] && a[i-len[i]]<=a[i-len[i]+2])这里多出的判断a[i-len[i]]<=a[i-len[i]+2]即为该題的限制从左到中保证身高不降，，因在回文串的计算过程中添加了额外的字符，所以这里是i-len[i]+2而不是i-len[i]+1，以避开添加的字符。#include<iostream>using namespace std;#define N 100010int len[N<<1];int a[N<<1];int Manacher(int n){int i,ans,mx,po;ans=po=mx=0;for(i=1;i<=(n<<1)+2;i++){if(mx>i)len[i]=mx-i<len[(po<<1)-i]?mx-i:len[(po<<1)-i];elselen[i]=1;while(a[i-len[i]]==a[i+len[i]] && a[i-len[i]]<=a[i-len[i]+2]) //因为有填充字符'#'，所以要+2。len[i]++;if(i+len[i]>mx){mx=i+len[i];po=i;}ans=ans>len[i]?ans:len[i];}return ans-1;}int main(){int T,n,i;scanf("%d",&T);while(T–){scanf("%d",&n);a[0]=-100;for(i=1;i<=n<<1;i+=2){a[i]=-200;//相当于'#'scanf("%d",&a[i+1]);}a[i]=-200;//相当于'#'a[i+1]=-300;printf("%d\n",Manacher(n));}return 0;}
没有伞的孩子必须努力奔跑!
