思路 最长上升子序列

• 限制
  • 每个城市之间只能建一座桥
  • 所有桥之间不能相交
• 按照自变量的大小把因变量排序，然后求最长上升子序列
  • 
• pair 默认对first升序，当first相同时对second升序

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

const int N = 5010;
PII q[N];
int f[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &q[i].first, &q[i].second);

    sort(q + 1, q + n + 1);

    int res = 0;
    for (int i = 1; i <= n; i ++ ) 
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (q[j].second < q[i].second) 
                f[i] = max(f[i], f[j] + 1);

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

    printf("%d\n", res);

    return 0;
}