学步园

我直接讲思路：

我们建立一个辅助数组b[]

b[i]储存的就是长度为i的最长不下降子序列中的最后一个的最小值

那么我们得到一个数l，就查找b[]数组中≤l的元素，以最后一个为答案

可以得到最后一个数为l的最长链，我们假设这个最长链长x，然后b[x]=min(b[x],l);

这个算法是n^2的，

但我们可以发现b[]数组也是最长不下降子序列

那么我们就可以二分查找！

于是乎复杂度就变成了nlogn

我用wikioi1576测试0ms通过了

代码：

#include<cstdio>
using namespace std;
#define INF 1000000000
int a[5555],b[5555],max,n;
int find(int r,int l,int p)
{
	if( r == l ) return r;
	int mid = ((r+l)>>1)+(r+l)%2;
	if(b[mid] > p) return find(r,mid-1,p);
	else return find(mid,l,p);
}
int main()
{
	int x,y;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i] = INF;
	}
	b[1]=a[1]; 
	max=1;
	for(int i=2;i<=n;i++)
	{
		x=find(0,max,a[i]);
		x++;
		b[x]=b[x]>a[i]?a[i]:b[x];
		max=max<x?x:max;
	}
	printf("%d",max);
}