题目链接
题目大意：在两条平行线间连点，要在线不交叉的前提下尽可能多的连线，问最多能连多少条线。

这题是最长上升子序列(LIS)模板题，我们先给出最基础的 O ( n 2 ) O(n^2) O(n2)动态规划算法：

• 设a为一个序列，a[i]为序列a从左往右第i个元素；设dp[i]为----序列a中以元素a[i]结尾的所有子序列中的最大上升子序列
• 状态转移方程： dp[i] = max { dp[j] | j<i 且 a[j]<a[i] } + 1 ，( i从1到n，j从1到i-1 )
  模板如下：

int dp[505], a[505], maxlen, n;
void initOn2() //最长单调子序列(LIS)的O(n^2)动态规划算法
{   // dp[i] = max{dp[j] | j<i 且 a[j]<a[i]} + 1
    memset(dp,0,sizeof(dp));
    int i, j;
    dp[1]=1;
    for(i=2 ; i<=n ; i++)
    {
        int maximum=0;
        for(j=1 ; j<i ; j++)
        {
            if(a[j] < a[i])
                maximum = max(maximum, dp[j]);
        }
        dp[i] = maximum + 1;
        maxlen = max(maxlen,dp[i]);
    }
}

遇到数据范围较小的题目可以用上述方法

但是本题的数据范围比较大（500,000），所以我们采用时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)的优化方法

二分查找+模拟栈（可参考https://www.cnblogs.com/wxjor/p/5524447.html）：

• 用dp数组模拟一个栈，如果当前的元素a[i]比栈顶元素大，就要入栈，如果比栈顶元素小，就二分查找到第一个大于等于a[i]的数，然后用a[i]换掉查找到的数。

这个方法实现起来很容易，但是很难被理解。没关系，笔者找到了一篇梳理思维的博客，能够帮助理解：
参考博客：https://blog.csdn.net/qq_36523667/article/details/78631696

最后附上模板代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[500005], a[500005]; //dp[i]储存以a[i]结尾的整个字符串的最长单调子序列
int n,p,maxlen;
int binFind(int x, int l, int r) // 二分查找：下标范围l到r
{
    int mid;
    while(l<=r)
    {
        mid = (l+r)/2;
        if(dp[mid]==x)
            return mid;
        else if(dp[mid]<x)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l;
}
void initOnlogn() //最长单调子序列(LIS)的O(nlogn)优化-模拟栈
{
    dp[1] = a[1];
    maxlen = 1;
    int pos;
    for(int i=2 ; i<=n ; i++)
    {
        if( a[i] > dp[maxlen] )
        {
            maxlen++;
            dp[maxlen] = a[i];
        }
        else
        {
            pos = binFind(a[i], 1, maxlen);
            dp[pos] = a[i];
        }
    }
}
int main()
{
    int cnt=1;
    while(scanf("%d",&n)!=EOF )
    {
        for(int i=1 ; i<=n ; i++)
        {
            scanf("%d",&p);
            scanf("%d",&a[p]);
        }
        //initOn2();
        initOnlogn();
        printf("Case %d:\n",cnt++);
        if(maxlen==1)
            printf("My king, at most 1 road can be built.\n");
        else
            printf("My king, at most %d roads can be built.\n",maxlen);
        printf("\n");
    }
    return 0;
}