rqnoj-217-拦截导弹-最长不上升子序列以及不上升子序列的个数
最长上升子序列的O（n*log（n））算法。
不上升子序列的个数等于最长上升子序列的长度。
#include<string.h>#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;#define INF 9999999int dp[10001];int num[10001];int num2[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]),num2[i]=INF-num[i]; for(i=0;i<n;i++) { int mid=dos(num2[i]); dp[mid]=num2[i]; } cout<<tops; tops=0; for(i=0;i<n;i++) { int mid=dos(num[i]); dp[mid]=num[i]; } cout<<" "<<tops<<endl; } return 0;}