体悟：
其实根据提示 nlogn 大概知道是用LIS，，但是我还是打算标记序号之后排个序，，，然后发现对于反向的递减的LIS 难弄。。
然后看题解；
原来是求反向的LIS，，，
然后枚举每一个dp[I], 这样就能确保枚举的是中心点。。
还是没有想到啊。。
#include<bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)); #define sf scanf #define pf printf #define bug1 printf("bug1\n"); #define N 10005 #define M 55 #define LL long long #define inf 0x3f3f3f3f int n ; int d[N]; int a[N],b[N]; int dp1[N]; int dp2[N]; void LIS(int *a,int *dp){ int g[N]; mem(g,inf); for(int i=1;i<=n;++i){ int k=lower_bound(g+1,g+1+n,a[i])-g; dp[i]=k; g[k]=a[i]; } } int main(){ while(~sf("%d",&n)){ for(int i=1;i<=n;++i){ sf("%d",&a[i]); b[n-i+1]=a[i]; } LIS(a,dp1); LIS(b,dp2); int ans=0,maxx=-1; for(int i=1;i<=n;++i){ ans=min(dp1[i],dp2[n-i+1])*2-1; maxx=max(maxx,ans); } pf("%d\n",maxx); } }
