P1020

我的代码最后一个Hack测试点TLE了，点这里看记录

代码：

#include <algorithm>
#include <cstdio>
int a[100005],f[100005],n,h[100005];
bool cmp(const int& a,const int& b)
{
    return a>b;
}
int main()
{
    n=1;
    while (~scanf("%d",&a[n])) n++;
    n--;
    int i,j,len=1;
    f[1]=a[1];
    for (i=2;i<=n;i++)
    {
        if (a[i]<=f[len]) f[++len]=a[i];
        else
        {
            j=std::upper_bound(f+1,f+len+1,a[i],cmp)-f;
            f[j]=a[i];
        }
    }
    printf("%d\n",len);
    int t=1,s,x;
    h[1]=a[1];
    for (i=2;i<=n;i++)
    {
        s=0;  x=2e9;
        for (j=1;j<=t;j++)
          if (a[i]<=h[j] && h[j]<x)
          {
              s=j;  x=h[j];
          }
        if (s!=0) h[s]=a[i];
        else h[++t]=a[i];
    }
    printf("%d",t);
    return 0;
}