1.简述:
描述
给 n 个信封的长度和宽度。如果信封 a 的长和宽都小于信封 b ,那么信封 a 可以放到信封 b 里,请求出信封最多可以嵌套多少层。
数据范围: ,
要求:空间复杂度 ,时间复杂度 要求:空间复杂度 ,时间复杂度
输入描述:
第一行输入一个正整数 n ,表示信封的数量
后续 n 行每行输入两个正整数表示信封的长度和宽度
输出描述:
输出最多可以嵌套的层数
示例1
输入:
9
3 4
2 3
4 5
1 3
2 2
3 6
1 2
3 2
2 4
输出:
说明:
从里到外是 (1,2) (2,3) (3,4) (4,5)
示例2
输入:
输出:
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);
}
}
本文来自网络,不代表技术学习分享_CKX技术立场,转载请注明出处。