python/TangDou/XiTi/1280.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 5005;
pair<int, int> x[N]; //数据一对一对读入，用pair，或者创建一个struct
int f[N];

/*
回想LIS问题中，线性序列的下标是递增的，我们求的也是其中最长的递增子序列，与本题如出一辙。所以解决本题
只需要先对一边的坐标自小到大排序，排序后另一岸的友好城市成一个线性序列，求该序列的LIS长度即是本题的解。

这个太牛了，真的在竞赛现场能想出办法吗？难道训练多了就会了？
*/
int main() {
    //输入+输出重定向
    freopen("../1280.txt", "r", stdin);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i].first >> x[i].second;
    //按pair的first进行排序，那么second自动配合上
    sort(x + 1, x + 1 + n);

    //输出看一下
    for (int i = 1; i <= n; ++i) {
        cout << x[i].first << "," << x[i].second << "           ";
    }
    cout << endl;

    //转化为最长上升子序列问题
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (x[i].second > x[j].second) f[i] = max(f[i], f[j] + 1);
        }
    }
    int res = 0;

    //找出最大值
    for (int i = 1; i <= n; i++) res = max(res, f[i]);
    cout << res << endl;

    //关闭文件
    fclose(stdin);
    return 0;
}