AcWing 1012. 友好城市

一、题目分析

二、实现代码

#include 

using namespace std;

//友好城市

//线段，二维，一般用PII,因为可以不需要写cmp，直接按first排序
typedef pair PII;

const int N = 5010;
PII a[N];   //南岸和北岸的一对友好城市的坐标
int f[N];   //记录以f[i]为结尾的一对友好城市时的，不产生交叉的最多城市对数
int n;      //n组友好城市

int main() {
    cin >> n;
    //读入友好城市对
    for (int i = 1; i <= n; i++)cin >> a[i].first >> a[i].second;
    //按first排序,则南岸城市坐标由小到大
    sort(a + 1, a + 1 + n);
    
    int res = 0;
    //LIS 正向
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            //业务要求，如果南岸城市坐标由小到大，那么北岸也必须由小到大，否则就是交叉
            if (a[i].second > a[j].second)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    printf("%d\n", res);
    return 0;
}