俄罗斯套娃问题

　

俄罗斯套娃

https://blog.csdn.net/lsjweiyi/article/details/70879776

【题目】

输入：第一行 n ,表示有n个套娃。之后n行，每行两个整数：分别表示宽和高。

只有宽和高都大于的才能嵌套。

输出：嵌套的最大层数。

提示：插入排序+LIS算法（最大上升子序列）

【解答】

方法一：暴力算法，空间复杂度为O（1）（不算读取数据的数组）。时间复杂度：O（n*n）。

import java.util.scanner;
public class RussiaPutBaby1 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextint();
        int[] wide=new int[n];
        int[] high=new int[n];
        for(int i=0;i<n;i++){
            wide[i]=sc.nextInt();
            high[i]=sc.nextInt();
        }
        System.out.println(Solution(n, wide, high));
    }

    static int Solution(int n,int[] wide,int[] high){//n^2
        int max=0;//记录嵌套的最大值
        int levels;//以某一个为基础的情况下套下的层数
        for(int i=0;i<n;i++){
            levels=0;
            //以一个套娃为基础，算算有多少能被他嵌套的（这里貌似是有问题的，重点看下一种方法）
            for(int j=0;j<n;j++){
                if(wide[i]>wide[j] && high[i]>high[j])
                    levels++;
            }
            max=max>levels?max:levels;
        }
        return max;
    }
}

方法二：先用宽进行排序，再对高求LIS。

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();

        int[] wide=new int[n];
        int[] high=new int[n];
        int w;
        int h;
        int index;
        for(int i=0;i<n;i++){
            index=i;
            w=sc.nextInt();
            h=sc.nextInt();
            while(index!=0 && w<wide[index-1]){//插入排序
                wide[index]=wide[index-1];
                high[index]=high[index-1];
                index--;
            }
            wide[index]=w;
            high[index]=h;
        }
        System.out.println(Solution(n, high));
    }

    //最长递增子序列问题（俄罗斯套娃问题：先按宽排序，再按高求LCS）
    public static int lis(int[] arr){
        if(arr == null || arr.length == 0)
            return 0;
        return lis(arr, arr.length);
    }

    private static int lis(int[] arr, int length){
        int lis[] = new int[length];//以i元素结尾的最长递增长度
//        for(int i = 0; i < length; i++)
//            lis[i] = 1;
        Arrays.fill(lis, 1); //初始化

        for(int i = 1; i < length; i++)
        {
            for(int j = 0; j < i; j++)
            {
             //lis[i]=max{lis[i-1], lis[i-1]+1}
                if(arr[i] > arr[j] && lis[j] + 1 > lis[i])
                    lis[i] = lis[j] + 1;
            }
        }

        int max = lis[0];
        int index = 0; //最长递增子序列末尾元素
        for(int i = 1; i < length; i++)
            if(max < lis[i]){
                max = lis[i];
                index = i;
            }
        System.out.println("末尾元素是：" + arr[index]);
        return max;
    }

相关阅读

对hanoi问题的理解

首先，我谈一下自己对原版hanoi问题递归公式的推导。优秀的理解网址，有图形我按照他的，也就是将A上的n个圆盘（编号从下往上是n->1）通过B

做私域流量前，先想想这三个问题

自从微信封杀朋友圈诱导分享后，运营的裂变之道开始寻求一条新出路，而私域流量成为了解决这个问题的答案。但是提到私域流量的人很多

解决sql server2008数据库安装之后，web程序80端口被占

前言： 原来电脑上的Apache一直使用正常，在安装sql server2008后，突然发现Apache无法启动，检查了一下是因为80端口被强制占用了。 解

关于无法进入电子科大信息门户的相关问题研究

关键词： 电子科大信息门户进不去   192.168.1.1用户名或密码有误   路由器设置经验1：如果按官方给出的两个方法做了还是进不去

0-1背包问题、贪心算法、动态规划

1、0-1背包问题  0-1背包问题：有一个贼在偷窃一家商店时，发现有n件物品，第i件物品价值vi元，重wi磅，此处vi与wi都是整数。他希望带走