侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-10 / 0 评论 / 0 点赞 / 82 阅读 / 869 字
温馨提示:
本文最后更新于 2023-02-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1012. 友好城市 - AcWing题库


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

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

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

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

输入格式

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

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

输出格式

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

数据范围

1N50001 \le N \le 5000 ,
0xi100000 \le x_i \le 10000

输入样例:

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

输出样例:

4

解题

方法一:动态规划

思路

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

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

具体见下图:

image-20230210043820408

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

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

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

参考: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);
    }
}
0

评论区