拿到题我们先想能不能dfs做，不行的话在考虑dp，最后再考虑贪心

在最长上升子序列模型中，dp的时间复杂度是O(n^2)，贪心的时间复杂度是O(nlogn)

/*
 * @Author: YMYS
 * @Date: 2024-12-17 08:44:40
 * @LastEditTime: 2024-12-19 09:42:15
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\2.最长上升子序列模型\4.友好城市.cpp
 * @URL:https://www.acwing.com/problem/content/1
 * @Description: 1012. 友好城市
 * 
 * 拿到题我们先想能不能dfs做，不行的话在考虑dp，最后再考虑贪心
 * 
 * 首先，题目给的是两个乱序的数组，我们想要套模型发现无从下手。
 * 因此我们必须保证有一个数组在某一方面是有序的，
 * 我们发现因为两个数组中的数是一一对应的，因此我们可以设置自变量和因变量，
 * 根据自变量的数值大小，去新增一个因变量的属性：大小顺序
 */
#include<bits/stdc++.h>

#define x first 
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
int w1[N], w2[N], f[N], g[N];
PII pii[N];

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>w1[i]>>w2[i];
        pii[i].x = w1[i];
        pii[i].y = w2[i];
    }

    //sort函数区间为【左闭右开】！！！！！
    sort(pii, pii+n+1);

    //我们对第二个数组，也就是因变量进行排序。
    //后续也拿这个因变量去进行LIS算法
    for(int i=1;i<=n;i++) f[i] = pii[i].y;

    for(int i=1;i<=n;i++){
        g[i] = 1;
        for(int j=1;j<i;j++){
            if(f[i]>f[j]){
                g[i] = max(g[i], g[j]+1);
            }
        }
    }

    //find_max
    int res = 1;
    for(int i=1;i<=n;i++){
        res = max(res, g[i]);
    }

    cout<<res<<endl;

    return 0;
}