Hdu-1025 Constructing Roads In JGShining's Kingdom (LIS)

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

题目大意：
每个偏僻城市可以接受繁荣城市的援助，但是相互之间的援助不能交差，
如图所示的援助是非法的

分析：
显然是直接做一个LIS，最长上升子序列，但是这题的数据量有些大，直接$n^2$dp是过不去的，所以需要优化成$nlogn$，看刘汝佳的代码比较清楚,g[i]表示长度为i的子序列的最小结尾，dp[i]表示以i为结尾，递增子序列的最大长度，最后要注意这题容易输出错误，只有一条路时输出1 road，超过1条路则输入k roads，算一个坑点

代码：

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

const int maxn = 520000;
const int INF = 0x3f3f3f3f;
int n,p,r;
int arr[maxn],g[maxn],dp[maxn];

int main()
{
    int t = 1 ;
    while (~scanf("%d",&n))
    {
//        if (t!=1)
//            putchar('\n');
        for (int i = 1 ; i <= n ; i ++)
        {
            scanf("%d%d",&p,&r);
            arr[p] = r;
        }
        memset(g,0x3f,sizeof(g));
        memset(dp,0,sizeof(dp));

        for (int i = 1 ; i <= n ; i ++)
        {
            int pos = lower_bound(g+1,g+n+1,arr[i])-g;
            dp[i] = pos;
            g[pos] = arr[i];
        }

        int maxx  =0 ;
        for (int i = 1 ; i <= n ; i ++)
            maxx = max(maxx,dp[i]);
        printf("Case %d:\n",t++);
        if (maxx==1)
            printf("My king, at most %d road can be built.\n\n",maxx);
        else
            printf("My king, at most %d roads can be built.\n\n",maxx);
    }

    return 0;
}