记录编号	253573	评测结果	AAAAAAAAAA
题目名称	[RQNOJ 167] 免费午餐	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2016-04-22 13:51:47	内存使用	1.06 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 100000+1000
#define INF 1<<30
using namespace std;
int g[maxn]={0},f[maxn]={0};
/*int lower_bound(int x,int n){
	int l=1,r=n,mid=(l+r)/2;
	while (l<r){
		mid=(l+r)/2;
		if (g[mid]>x) l=mid;
		else r=mid-1;
	}
	return r;
}*/
int main(){
	freopen("lunch.in","r",stdin);
	freopen("lunch.out","w",stdout);
	int n,k;
	scanf("%d",&n);
	for (int i=n+1;i>=2;i--) scanf("%d",&f[i]);
	f[1]=0;
	n++;
	int t=0,ans=0;
	for (int i=1;i<=n;i++) g[i]=INF;
	for (int i=1;i<=n;i++){
		t=lower_bound(g+1,g+1+n,f[i])-g;
		g[t]=f[i];
		ans=max(t,ans);
	}
	printf("%d",ans-1);
	return 0;
}