记录编号	260412	评测结果	AAAAAAAAAA
题目名称	[RQNOJ 167] 免费午餐	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	0.063 s
提交时间	2016-05-13 18:46:37	内存使用	0.97 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int SIZEN=100010,INF=0x7fffffff/2;
int N;
int a[SIZEN];
void read()
{
	scanf("%d",&N);
	for(int i=N;i>=1;i--) scanf("%d",&a[i]);
}
int G[SIZEN];
void work()
{
	for(int i=1;i<=N;i++) G[i]=0;
	G[0]=-INF;
	int len=0;
	for(int i=1;i<=N;i++)
	{
		if(a[i]==0) continue;
		int k=lower_bound(G,G+1+len,a[i])-G;
		if(k>len) len=k;
		G[k]=a[i];
	}
	printf("%d\n",len);
}
int main()
{
	freopen("lunch.in","r",stdin);
	freopen("lunch.out","w",stdout);
	read();
	work();
	return 0;
}