求最长升序子序列O(nlgn)的算法---HDOJ 1025
求解最长升/降序子序列是动规的经典问题，朴素动规的时间复杂度为O(n^2)，
状态的转移方程为dp[i]=max{dp[j]}+1，其中j<i且arr[j]<arr[i];
现在我们对上面的转移方程再做一个限定，当有多个j满足条件时，
即有多条转移路径的时候，我们规定选择从元素值最小的那个状态转移，
并且用一个数组min[k]来保存dp值为k的最小元素，这样min数组的值
是单调递增的，所以在计算dp[i]时就可以用二分代替线性扫描，从而
将复杂度降低至lgn，这样，总的复杂度变成了nlgn.
#include<cstdio>#include<algorithm>#define N 500500using namespace std;struct road{ int x,y; bool operator < (const road &a) const { return x<a.x; }}arr[N];int n,dp[N],marr[N],len,inf;int bs(int *a,int s,int e,int k){ int mid=(s+e)>>1; if(a[mid]<=k && mid>=e) return mid; if(a[mid]<=k && k<a[mid+1]) return mid; if(a[mid]>k) return bs(a,s,mid-1,k); else return bs(a,mid+1,e,k);}void dpro(void){ for(int i=1;i<=n;i++) if(arr[i].y<inf) inf=arr[i].y; inf--; marr[0]=inf; len=0; for(int i=1;i<=n;i++) dp[i]=1; for(int i=1;i<=n;i++) { int idx = bs(marr,0,len,arr[i].y); marr[idx+1]=arr[i].y; if(idx==len) len++; dp[i]=idx+1; }}int main(){ int cas=1; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d%d",&arr[i].x,&arr[i].y); sort(arr+1,arr+n+1); dpro(); int max=0; for(int i=0;i<n;i++) if(max<dp[i]) max=dp[i]; printf("Case %d:\n",cas++); printf("My king, at most %d road",len); if(len>1) printf("s"); printf(" can be built.\n\n"); } return 0;}