$$\color{Red}{友好城市-排序上升子序列}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。

北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

输入格式
第1行，一个整数N，表示城市数。

第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出格式
仅一行，输出一个整数，表示政府所能批准的最多申请数。

数据范围

1 ≤ N ≤ 5000

0 ≤ xi ≤ 10000

输入样例：

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出样例：

4

简单证明思路

看到这道题的直觉做法：
两岸的点都从大到小排序，然后最大的组合点，肯定是一个递增的链接，即上1连下2，上2连下3 ····，上n-1连下n。

但是图中的连接方式已经给定了，所以我们只能先排序一岸，另外一岸的连接相当于一条连接线，那么我们需要按自变量，选择因变量，选没有交叉的最多连接路径。显然，合法的连接是一个上升子序列，一旦出现更小数目，即产生交叉。而上升子序列的最大数，显然就是本题的答案。因此，我们只需要绑定点在一个元组里，然后按上述做法进行最长上升子序列判断。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;


public class Main {
    static int N = 5010, n;
    static int[] f = new int[N];

    static class Node {
        int a, b;

        public Node(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
    static Node[] nodes = new Node[N];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int res = 0;
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String [] str = br.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            nodes[i] = new Node(a, b);
        }
        Arrays.sort(nodes, 0, n, Comparator.comparingInt(o -> o.a));
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nodes[i].b > nodes[j].b) 
                    f[i] = Math.max(f[i], f[j] + 1);
            }
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }
}

python代码

N = 5010
f = [1] * N
edge = []
n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    edge.append([a, b])
# 自变量排序，因变量求最长上升子序列
res = 0
edge.sort(key = lambda x: x[0])
for i in range(n):
    for j in range(i):
        if edge[i][1] > edge[j][1]:
            f[i] = max(f[i], f[j] + 1)
    res = max(res, f[i])

print(res)