本题从后往前和从前往后分别求一遍LIS;
朴素LIS的dp算法为o(n^2)用,set<node> node里结点先按高度排,再按该结点最大LIS 长度排序;动态维护每个H 下的最大LIS;并删除相对较劣元素
#include<cstdio> #include <vector> #include<cstring> #include<iostream> #include <set> #include <algorithm> using namespace std; #define INF 1000000; const int maxn = 10010; struct node{ int H,premax; node(int x=0,int y=0):H(x),premax(y){} bool operator <(const node& rhs) const{ return H < rhs.H||H == rhs.H && premax < rhs.premax; } }; set<node> V1; set<node> :: iterator p,p1,p2,p3; int a[maxn],n,pd[maxn],sd[maxn],ta[maxn]; int main() { while(scanf("%d",&n)==1){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1,j=n;i<=n;i++,j--) ta[j]=a[i]; pd[1]=1; V1.clear(); V1.insert(node(a[1],pd[1])); for(int i=2;i<=n;i++){ p=V1.lower_bound(node(a[i],0)); if(p!=V1.begin()) { p1=p; p1--; pd[i]=p1->premax+1; } else pd[i]=1; if(p!=V1.end()){ p2=p; for(;;){ if(p2==V1.end()) break; if(p2->premax > pd[i]) break; else { p1=p2++; V1.erase(p1); } } } V1.insert(node(a[i],pd[i])); } sd[1]=1; V1.clear(); V1.insert(node(ta[1],sd[1])); for(int i=2;i<=n;i++){ p=V1.lower_bound(node(ta[i],0)); if(p!=V1.begin()) { p1=p; p1--; sd[i]=p1->premax+1; } else sd[i]=1; if(p!=V1.end()){ p2=p; for(;;){ if(p2==V1.end()) break; if(p2->premax > sd[i]) break; else { p1=p2++; V1.erase(p1); } } } V1.insert(node(ta[i],sd[i])); } for(int i=1,j=n;i<j;i++,j--){int temp=sd[i]; sd[i]=sd[j]; sd[j]=temp;} int RES=1; for(int i=1;i<=n;i++){ int num=min(pd[i],sd[i]); RES=max(RES,num*2-1); } printf("%d\n",RES); } return 0; }