题意简述

有一条河，河的南北两岸各有N座城市。这些城市两两之间可以建一座桥，但建的桥不能交叉，问最多可以建几座桥。

思路

这里的我们可以先想想交叉和不交叉的情况下分别画出来的图是什么样子的。

我们可以发现，在两座桥不交叉的情况下，有$a_1 < a_2, b_1 < b_2$，在两座桥相交的情况下，有$a_1 < a_2, b_2 < b_1$。

所以我们可以发现两桥是否交叉是可以用北岸城市编号的大小关系给反应出来的。

所以我们的思路就可以转化为以南岸的城市编号为基准，把所有的城市对从小到大排序，从而得到关于北岸城市的一个数组。因为当$b_i < b_j$时能成功建一座桥，所以问题就转化成了求取这个数组的最长上升子序列。

到此，我们对北方城市的数组做一次$\ LIS\ $就可以得到答案了。

复杂度分析

• 时间复杂度：$O(N ^ 2)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;         //双数据排序的最好方式就是pair

const int N = 5010;

int n;
PII p[N];
int f[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> p[i].first >> p[i].second;

    sort(p + 1, p + 1 + n);
    int ans = 0;
    for(int i = 1; i <= n; i++)     //常规的LIS操作
    {
        f[i] = 1;
        for(int j = 1; j < i; j++)
            if(p[i].second > p[j].second)
                f[i] = max(f[i], f[j] + 1);

        ans = max(ans, f[i]);
    }

    cout << ans << endl;
    return 0;
}