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);
}
}