1. 题目

1. 题目描述

搜狐员工小王最近利用假期在外地旅游，在某个小镇碰到一个马戏团表演，精彩的表演结束后发现团长正和大伙在帐篷前激烈讨论，小王打听了下了解到， 马戏团正打算出一个新节目“最高罗汉塔”，即马戏团员叠罗汉表演。考虑到安全因素，要求叠罗汉过程中，站在某个人肩上的人应该既比自己矮又比自己瘦，或相等。 团长想要本次节目中的罗汉塔叠的最高，由于人数众多，正在头疼如何安排人员的问题。小王觉得这个问题很简单，于是统计了参与最高罗汉塔表演的所有团员的身高体重，并且很快找到叠最高罗汉塔的人员序列。 现在你手上也拿到了这样一份身高体重表，请找出可以叠出的最高罗汉塔的高度，这份表中马戏团员依次编号为1到N。

2. 输入

首先一个正整数N，表示人员个数。 
之后N行，每行三个数，分别对应马戏团员编号，体重和身高。

3. 输出

正整数m，表示罗汉塔的高度。

4. 示例

输入

输出

2. 题目分析

有一说一，我拿到这个题目的时候，想众筹给出提的人报个语文补习班(小声bb)~
那么这道题要干什么呢？叠罗汉，我相信大家都看过叠罗汉，那么我们知道为了安全下面人的体重要更重，身高要更高，没错这道题也是这么规定的(看来还是很贴近生活的，就是没说清楚而已，别骂了别骂了)，那么我们怎么做呢？我们可以先想简单一点，一组有序的数字，从小到大排列，那么用这组数组来叠罗汉最大高度一定是数组的长度，对吧。
那我们也可以给这群马戏团的表演者排个序啊，我们先按照身高从小到大来排序，这个时候越靠前的表演者越低，那这个时候只需要通过比较体重来判断下一个表演者能否叠上去对吧。
也就是说我们需要将整个"人"类型的数组排序，不难看出这其实就是一个 0 - 1 背包问题，有两种情况，这个演员叠与不叠，所以这道题就是动态规划求解。
那么怎么排序呢？我们知道 Arrays.sort() 这个方法是用来给数组排序的，但是怎么能让一个身高，一个体重两个变量排序呢？那么请问身高和体重是谁的属性？人啊~所以我们可以定义一个人类型，有身高和体重两个成员属性。
那又有人问了：怎么给这群人排序呢？Arrays.sort() 是可以传一个 Comparator 比较器的，根据这个比较器的规则来排序，那么我们说了先给这群人按照身高排序，如果身高相等按照体重排序，如果体重相等，那还排什么啊，两个人都一样重一样高了，上面下面无所谓了呀。
那么排完序了，怎么搞啊？我们是按照身高由低到高排序的，那么我们遍历这个数组，以第 i 个为底下的人，让前 j = i - 1 个在上面，那么数组时升序的，第 j 个的一定第 j 个矮，所以只需要比较体重，第 j 个比第 i 个轻就可以叠上去，或者身高体重完全一样也可以叠上去，使用一个int数组来记录以第 i 个为最下面一个人时的最大高度。

请添加图片描述

现在排完序了我们来确定转移方程：每个dp的元素初始值为 1 ，就算叠不上去，它自己本身也算一个高度，由于数组按照身高排序，当满足 i 的体重大于 j 的体重这个条件时，dp[i] = Math.max(dp[i],dp[j] + 1)，i 表示当前为最底下的人，j 表示当前判断是否能叠上去的人，不满足时，这个人就跳过了。

3. 代码实现

紧张刺激的代码环节

import java.util.*;

public class Main {
    static class People {
        public int height;
        public int weight;
        public People(int weight, int height) {
            this.height = height;
            this.weight = weight;
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()) {
            int num = scan.nextInt();
            People[] peoples = new People[num];
            for (int i = 0; i < num; i++) {
                // 并没有明确说明是按顺序输入
                int index = scan.nextInt();
                peoples[index - 1] = new People(scan.nextInt(), scan.nextInt());
            }
            // 按身高排序
            Arrays.sort(peoples,new Comparator<People>(){
                public int compare(People p1, People p2) {
                    int res = Integer.compare(p1.height, p2.height);
                    if (res != 0) {
                        return res;
                    } else {
                        return Integer.compare(p1.weight, p2.weight);
                    }
                }
            });
            int[] dp = new int[num];
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < num; i++) {
                dp[i] = 1;
                for (int j = i - 1; j >= 0; j--) {
                    if (peoples[i].weight > peoples[j].weight ||
                            (peoples[i].weight == peoples[j].weight) && peoples[i].height == peoples[j].height) {
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                    }
                    max = Math.max(max, dp[i]);
                }
            }
            System.out.println(max);
        }
    }
}