题目大意:
给定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); } }