rqnoj-156-吞噬比赛-最长上升子序列O(nlog(n))算法

最长上升子序列的O(nlog(n))算法，简单实用，必备佳品

#include<string.h>#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;int dp[10001];int num[10001];int tops;int dos(int x){    if(tops==0)    {        tops++;        return 0;    }    if(x<dp[0])return 0;    if(x>dp[tops-1])    {        tops++;        return tops-1;    }    int mid,l,r;    l=0;r=tops;    mid=(l+r)/2;    while(l<r)    {        if(dp[mid]>x)r=mid;        if(dp[mid]<x)l=mid+1;        if(dp[mid]==x)return mid;        mid=(l+r)/2;    }    return mid;}int main(){    int n,i;    while(~scanf("%d",&n))    {        tops=0;        for(i=0;i<n;i++)scanf("%d",&num[i]);        for(i=0;i<n;i++)        {            int mid=dos(num[i]);            dp[mid]=num[i];        }        cout<<tops<<endl;    }    return 0;}