记录编号	38892	评测结果	AAAAAAAAAA
题目名称	[RQNOJ 167] 免费午餐	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.074 s
提交时间	2012-06-20 13:45:20	内存使用	1.43 MiB

#include <cstdlib>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN=100011;
int F[MAXN]={0},A[MAXN],S[MAXN],N;
int L,R,Mid,now;
 
inline int max(int a,int b)
{
    return a>b?a:b;
}
 
inline int find(int k)
{
    L=1,R=now,Mid=(L+R)/2;
    while(L<=R)
    {
        if(S[Mid]>k) L=Mid+1;
        else R=Mid-1;
        Mid=(L+R)/2;
    } return Mid;
}
 
int main()
{ 
    freopen("lunch.in","r",stdin);
    freopen("lunch.out","w",stdout);
    scanf("%d\n",&N);
    for(int i=1;i<=N;i++) scanf("%d",&A[i]),S[i]=0; 
    if(A[1]!=0) {S[1]=A[1]; F[1]=1; now=1;}
    int tmp;
    for(int i=2;i<=N;i++)
    {
        if(A[i]==0) continue;
        tmp=find(A[i])+1;
        if(tmp>F[i]) F[i]=tmp;
        if(tmp>now) now=tmp;
        if(S[F[i]]<A[i]) S[F[i]]=A[i];
    }
    printf("%d\n",*max_element(F+1,F+1+N));
    return 0;
}