hdu 1025（最長非遞減子序列的n*log(n)求法）

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1025

經典題。。。最長非遞減序列的n*log(n)求法。。。orz...

#include<iostream>
const int N=500007;
using namespace std;
int city[N];
int dp[N];//dp[i]保存的是長度為i的最長不降子序列的最小尾元素

//二分查找返回num在dp中的位置
int Search(int dp[],int len,int num){
    int low=1,high=len;
    while(low<=high){
        int mid=(low+high)/2;
        if(num==dp[mid])return mid;
        else if(num<dp[mid])high=mid-1;
        else if(num>dp[mid])low=mid+1;
    }
    return low;
}

int main(){
    int n,_case=1;
    while(~scanf("%d",&n)){
        int a,b;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a,&b);
            city[a]=b;
        }
        dp[0]=-1,dp[1]=city[1];
        int len=1;
        //n*log(n)求最長單調非遞減序列
        for(int i=1;i<=n;i++){
            int j=Search(dp,len,city[i]);
            dp[j]=city[i];//每次都要更新dp
            if(j>len)len++;
        }
        printf("Case %d:\n",_case++);
        if(len==1){
            printf("My king, at most %d road can be built.\n\n",len);
        }else 
            printf("My king, at most %d roads can be built.\n\n",len);
    }
    return 0;
}


            

?