hdu 6592 Beauty Of Unimodal Sequence

首先前后各跑一遍LIS ，然后即可找到最长的子序列长度和中间值，对于中间值两边的直接选取和用单调栈来实现字典序 

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int inf = 0x3f3f3f3f;

ll n,a[300005],pos[300005];
ll dp[300005],ans1[300005],ans2[300005]; 
stack<ll> st;
vector<ll> vec,v;
int main(){
	while(scanf("%lld",&n)>0){
		memset(dp,inf,sizeof(ll)*(n+1));
		dp[0]=0;
		for(int i=1;i<=n;i++){
			scanf("%lld",a+i);
			pos[i]=inf;
			ans1[i]=0,ans2[i]=0;
			ans1[i] = lower_bound(dp+1,dp+n+1,a[i])-dp;
			dp[ans1[i]]=a[i];
		}
		memset(dp,inf,sizeof(ll)*(n+1));
		dp[0]=0;
		for(int i=n;i>0;i--){
			ans2[i] = lower_bound(dp+1,dp+n+1,a[i])-dp;
			dp[ans2[i]]=a[i];
		}
		while(!st.empty()) st.pop();
		ll mx = ans1[1]+ans2[1],idx=1;
		//字典序最小   ans1[1]为1  ans2[1]为a[1]右边比a[1]大的数的个数  mx即为最长子序列的长度 
		for(int i=2;i<=n;i++){
			if(ans1[i]+ans2[i]>mx){
				mx = ans1[i]+ans2[i];
				idx = i;
			}
		}
		pos[ans1[idx]]=a[idx]; //找到序列中最大的值 至pos中  
		for(int i=idx-1;i>=1;i--){
			if(ans1[i] > ans1[idx] ) continue;
			if( a[i] >= pos[ans1[i]+1] ) continue;
			//找到最小序列    
			while(!st.empty()&& ans1[i] >= ans1[st.top()]){
				st.pop();
			}
			st.push(i);//将符合条件的存入栈中 
			pos[ans1[i]] = a[i];
		} 
		v.clear();
		while(!st.empty()){
			v.push_back(st.top());
			st.pop();
		}
		v.push_back(idx);
		int x=idx;
		for(int i=idx+1;i<=n;i++){
			//将idx后的lis序列恰好大于1 存入其下标 ，即为字典去最小 
			if(ans2[x] == ans2[i] + 1  /*&& a[i] < a[x] */){
				v.push_back(i);
				x=i;
			}
		}
		for(int i=0;i<v.size();i++){
		 i==0? (cout << v[i] ) : (cout << " " <<v[i]) ;
		}
		cout << endl;
		
		
		//字典序最大 
		v.clear();
		while(!st.empty()) st.pop();
		mx=ans1[1]+ans2[1];  idx=1;
		for(int i=2;i<=n;i++){
			if(ans1[i]+ans2[i]>=mx){
				mx = ans1[i]+ans2[i];
				idx = i;
			}
		}
		
		x=idx;
		v.push_back(idx);
		for(int i=idx-1;i>=1;i--){
			if(ans1[x] == ans1[i]+1  ){
				v.push_back(i);
				x=i;
			}
		}
		reverse(v.begin() , v.end());
		
		int flag=0;
		for(int i=0;i<v.size();i++){
			if(flag) cout << " ";
			flag=1;
			cout << v[i] ;
		}
		memset(pos,inf,sizeof(ll)*(n+1));
		pos[ans2[idx]]=a[idx];
		for(int i=idx+1;i<=n;i++){
			if(ans2[i] > ans2[idx] ) continue;
			if( a[i] > pos[ans2[i]+1] ) continue;
			while(!st.empty()&& ans2[i] >= ans2[st.top()]){
				st.pop();
			}
			st.push(i);
			pos[ans2[i]] = a[i];
		} 
		v.clear();
        while(!st.empty()) {
            v.push_back(st.top());
            st.pop();
        }
        reverse(v.begin(),v.end());
        for(int i=0;i<v.size();i++){
			if(flag) cout << " ";
			flag=1;
			cout << v[i] ;
		}
		cout << endl;
		
	} 
}