闫式dp分析法

/*
    题目分析 ： experience 做法
            条件 1 : 所有城市之间只能有一座桥
                 2 : 所有城市的桥不能相交


            1) 将一端排好序，求另外一端的最长上升子序列
                1-1) 通过排序固定自变量，求另外一端的最长上升子序列

                2 1 5 3 6 4
                1 2 3 4 5 6

*/


 二分 + 贪心做法
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 5010;
PII q[N];
int f[N];
int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);

    cin >> n;
    for (int i = 1 ; i <= n ; i ++ ) cin >> q[i].x >> q[i].y;

    sort(q + 1 , q + n + 1);
    int len = 0;
    for (int i = 1 ; i <= n ;i ++ ) {
        int l = 0 , r = len;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (f[mid] < q[i].y) l = mid;
            else r = mid - 1;
        }
        f[r + 1] = q[i].y;
        len = max(len,r + 1);

    }

    cout << len;
    return 0;
}