题目大意:
给定n个正整数的数列 找最长对称的子序列,且从左往右递增
T<20行测试样例
1 <= n <= 100000,50 <= a[i]<= 250;
一 马拉车有俩个判断点
(一) 这个点是否在这个对称中心的范围内
1 如果在 那么有两个条件 (1) 对称点的范围在对称中心内
(2) 对称点的范围大于对称中心
1 如果不再那么 按照朴素方法扩展
这几种条件 有个共同点是范围内加 超出 扩展 所以可以合并条件
ac代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005*2],vis[1000005*2];
void namachear(){
int po=1,mx=1;
vis[1]=1;
for(int i=2;i<=2*n;i++){
vis[i]=i<mx?min(mx-i,vis[po*2-i]):1;
while(a[i-vis[i]]==a[i+vis[i]]&&a[i+vis[i]-2]>=a[i+vis[i]]){
vis[i]++;
}
if(i+vis[i]>mx){
mx=i+vis[i];
po=i;
}
}
}
int main(){
int t;
cin>>t;
while(t--){
scanf("%d",&n);
for(int i=2;i<=n*2+1;i+=2){
scanf("%d",&a[i]);
a[i+1]=-1;
}
a[0]=-2;
a[1]=-1;
namachear();
int ans=0;
// for(int i=1;i<=n*2;i++)
// cout<<vis[i]<<' ';
for(int i=2;i<=2*n+1;i++)
ans=ans<vis[i]?vis[i]:ans;
printf("%d\n",ans-1);
}
} 
京公网安备 11010502036488号