AcWing——友好城市

2020-11-25

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

思路:
按照 PII 类进行存储以后,按 x 坐标排序以后,即在 y 坐标轴上跑一遍 LIS 即可,求一遍最长上升子序列即使答案,按照 x 坐标排序其实是为了满足拓扑序,而在 y 坐标上进行 DP 状态的转移其实是在满足 X 坐标的拓扑序的前提下,即在拓扑图上进行的状态转移 y 总 nb

Java 代码

import java.util.*;
/*

 */
class PII
{
    int x,y;
    public PII(int x,int y) {
        this.x=x;
        this.y=y;
    }
}
public class Main {
    private static final int N = 5100;

    static int []g=new int[N];
    static int []dp=new int[N];
    static PII []a=new PII [N];

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n;
        n=sc.nextInt();
        for(int i=1;i<=n;i++) {
            int x,y;
            x=sc.nextInt();
            y=sc.nextInt();
            a[i]=new PII(x,y);
        }
        //按x轴进行排序
        Arrays.sort(a,1,n+1,((o1, o2) -> o1.x-o2.x));

        //按y轴进行dp
        int res=1;
        for(int i=1;i<=n;i++) {
            int y=a[i].y;
            dp[i]=1;
            for(int j=1;j<i;j++) {
                if(a[j].y<y) {
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            res=Math.max(res,dp[i]);
        }
        System.out.println(res);
    }
}


标题:AcWing——友好城市
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2020/11/25/1606311719329.html