UVA 10354 nlogn LIS

本文主要是介绍UVA 10354 nlogn LIS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

nlogn的最长上升子序列（原理）。这是第一个trick。

第二个，要左边和右边的相同，枚举每一个点作为最高点时的情况。两边取较小的那个再乘以2。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define MS(x) memset(x,0,sizeof(x))int up[20000];
int down[20000];
int num[20000];
int rnum[20000];
int up2[20000];
int g[20000];
const int INF=0x3f3f3f3f;
int main()
{
//	freopen("acm.in", "r", stdin);int n;while(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++){scanf("%d",&num[i]);rnum[n-1-i]=num[i];}fill(g,g+n+1,INF);for(int i=0;i<n;i++){int p=lower_bound(g,g+n,num[i])-g;up[i]=p+1;g[p]=num[i];}fill(g,g+n+1,INF);for(int i=0;i<n;i++){int p=lower_bound(g,g+n,rnum[i])-g;up2[i]=p+1;g[p]=rnum[i];}int max_=1;for(int i=0;i<n;i++){max_=max(max_,min(up[i],up2[n-1-i])*2-1);}printf("%d\n",max_);	}	
//	fclose(stdin);
}

这篇关于UVA 10354 nlogn LIS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---