hdu1025（nlon(n)最长上升子序列）

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

大致思路：设置两个a,b数组，a数组存储数据，b数组存储最长不降序序列。此算法关键在于设计二分查找。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
using namespace std;
int dp[50500],a[50500];
int solve(int n)
{
    int len=1,low,high,mid;
    dp[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        low=1;high=len;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(a[i]>dp[mid])low=mid+1;
            else high=mid-1;
        }
        dp[low]=a[i];
        if(low>len)len=low;
    }
    return len;
}
int main()
{
    int n,x,y,cas=1;
    while(scanf("%d",&n)>0)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&x,&y);
            a[x]=y;
        }
        int ans=solve(n);
        printf("Case %d:
",cas++);
        if(ans==1)
             printf("My king, at most 1 road can be built.
");
        else
             printf("My king, at most %d roads can be built.
",ans);
         printf("
");
    }
}