【动态规划】友好城市「动态规划之LIS模型」

题目

1012. 友好城市 - AcWing题库

---

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

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

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

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

输入格式

第1行，一个整数N，表示城市数。

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

输出格式

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

数据范围

$1 \le N \le 5000$ ,
$0 \le x_i \le 10000$

输入样例：

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

输出样例：

4

解题

方法一：动态规划

思路

首先考虑一下一下暴力怎么做：很容易想到枚举所有的方案，然后检查方案是否合法，如果合法就考虑是否能够更新最大值答案，但这么做的时间复杂度是 $O(n^2)$，毫无疑问会超时。

所以就需要找出一些性质进行优化，既然是要暴力枚举，可以考虑一个枚举方案，按照上岸的坐标从小到大来枚举，这样就只需关心下岸的坐标之间有何关系即可。于是，可以轻易发现，上坐标从小到大枚举选择到的桥，其对应下坐标也必然是从小到大的。

具体见下图：

蓝色表示该方案按照上坐标从小到大先选出来的桥。
红色表示该方案的下一座桥的下坐标不是从小到大的，绿色表示是从小到大。

因此，该方案中，在上坐标排序的情况下，下坐标次序不是从小到大的，则必然不合法（会有相交）。
于是，这题就变成了：把桥一边坐标坐标从小到大排序后，对另一边的坐标求最长上升子序列。

模板：【动态规划】最长上升子序列。

参考：https://www.acwing.com/solution/content/51858/

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[][] a = new int[n][2];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i][0] = (int) in.nval;
            in.nextToken();
            a[i][1] = (int) in.nval;
        }
        Arrays.sort(a, (x, y) -> x[0] - y[0]);
        int[] f = new int[n];
        for (int i = 0; i < n; ++i) {
            f[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (a[j][1] < a[i][1]) f[i] = Math.max(f[i], f[j] + 1);
            }
        }
        int mx = 1;
        for (int x : f) mx = Math.max(mx, x);
        System.out.println(mx);
    }
}