【键值对 LIS】 友好城市

传送门

题意

给定 N 个数对，其中((x,y))分别表示一个相对的两岸，两者之间连一条线，不允许有交叉，问最多可以连多少

数据范围

(egin{array}{l}1 leq N leq 5000 \ 0 leq x_{i} leq 10000end{array})

题解

连线后不存在交叉，即对于键值对((x,y))来说，不会使得(x)在第一个键值中的次序和(y)的是逆序的
即两个格子的顺序都是单调的才可以
按照其中一个键值进行排序后，对另一个键值求最长上升子序列即可

Code

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define ll long long
#define fi first
#define se second
typedef pair<int,int>pii;
const int N=5010;
pii a[N];
int n,f[N];
int main(){
    scanf("%d",&n);
    rep(i,1,n+1) scanf("%d%d",&a[i].fi,&a[i].se);

    sort(a+1,a+n+1);
    int ans=-1;

    rep(i,1,n+1){
        f[i]=1;
        rep(j,1,i)
            if(a[j].se < a[i].se)
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    } 
    printf("%d
",ans);
}