技术学习分享_一航技术 技术资讯 #yyds干货盘点# 动态规划专题:信封嵌套

#yyds干货盘点# 动态规划专题:信封嵌套

广告位

1.简述:

描述

给 n 个信封的长度和宽度。如果信封 a 的长和宽都小于信封 b ,那么信封 a 可以放到信封 b 里,请求出信封最多可以嵌套多少层。

数据范围: #yyds干货盘点# 动态规划专题:信封嵌套 , #yyds干货盘点# 动态规划专题:信封嵌套

要求:空间复杂度 #yyds干货盘点# 动态规划专题:信封嵌套,时间复杂度 #yyds干货盘点# 动态规划专题:信封嵌套要求:空间复杂度 #yyds干货盘点# 动态规划专题:信封嵌套 ,时间复杂度 #yyds干货盘点# 动态规划专题:信封嵌套

输入描述:

第一行输入一个正整数 n ,表示信封的数量

后续 n 行每行输入两个正整数表示信封的长度和宽度

输出描述:

输出最多可以嵌套的层数

示例1

输入:

9
3 4
2 3
4 5
1 3
2 2
3 6
1 2
3 2
2 4

输出:

4

说明:

从里到外是 (1,2) (2,3) (3,4) (4,5)

示例2

输入:

2
1 4
4 1

输出:

1

2.代码实现:

import java.util.*;
public class Main{
public static void main(String []args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int [][]num=new int[n][2];
for(int i=0;i<n;i++){
num[i][0]=input.nextInt();
num[i][1]=input.nextInt();
}
Arrays.sort(num,new Comparator<int[]>(){
public int compare(int[] a,int[] b){
return a[0]==b[0]?a[1]-b[1]:a[0]-b[0];
}
});
//两个维度的最长上升子序列
int[]dp=new int[n];
Arrays.fill(dp,1);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if((num[j][0]>num[i][0])&&(num[j][1]>num[i][1])){
dp[j]=Math.max(dp[j],dp[i]+1);
}
}
}
int max=0;
for(int i=0;i<n;i++){
max=Math.max(max,dp[i]);
}
System.out.println(max);
}

}

本文来自网络,不代表技术学习分享_一航技术立场,转载请注明出处。

作者: 一航技术

上一篇
下一篇
广告位

发表回复

返回顶部