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;}