杭州打的样，适合全国推广

宫水三叶的刷题日记

发布于 2024-05-13 16:46:42

1470

发布于 2024-05-13 16:46:42

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

题目描述

平台：LeetCode

题号：1691

给你 n 个长方体 cuboids，其中第 i 个长方体的长宽高表示为

cuboids[i] = [width_i, length_i, height_i]

（下标从 0 开始）。

请你从 cuboids 选出一个「子集」，并将它们堆叠起来。

如果

width_{i} <= width_{j}

且

length_{i} <= length_{j}

且

height_{i} <= height_{j}

，你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。

返回堆叠长方体 cuboids 可以得到的最大高度。

示例 1：

输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]]

输出：190

解释：
第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。
第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。
第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。
总高度是 95 + 50 + 45 = 190 。

示例 2：

输入：cuboids = [[38,25,45],[76,35,3]]

输出：76

解释：
无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。

示例 3：

输入：cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]

输出：102

解释：
重新排列长方体后，可以看到所有长方体的尺寸都相同。
你可以把 11x7 的一面朝下，这样它们的高度就是 17 。
堆叠长方体的最大高度为 6 * 17 = 102 。

提示：

n = cuboids.length

1 <= n <= 100

1 <= width_{i}, length_{i}, height_{i} <= 100

排序 + 序列 DP

定义

f[i]

为考虑前

个箱子，且必须使用到第

个箱子的最大高度。

不难发现，

f[i]

至少为当前箱子中的最大边长，而所有

f[i]

的最大值即是答案。

由于题目规定了只有三边都不超过盒子 j 的盒子 i 才能放置在上面，因此我们可以先对三边总和进行「降序」排序。

这样当我们处理到盒子 i 时，所有能够位于盒子 i 底部的盒子 j 均位于 i 左侧，我们可以通过枚举

j \in [0, i - 1]

的盒子，用满足条件的盒子 j 来更新

f[i]

，即有

f[i] = \max(f[j] + height_i)

。

实现上，当我们在判定某个盒子 j 是否能够位于盒子 i 的底部时，并不需要枚举两盒子的旋转情况，可以在进行 DP 之前先对所有盒子进行排序预处理（按照升序排序）。

Java 代码：

class Solution {
    public int maxHeight(int[][] cs) {
        int n = cs.length;
        for (int i = 0; i < n; i++) Arrays.sort(cs[i]);
        Arrays.sort(cs, (a, b)->(b[0]+b[1]+b[2])-(a[0]+a[1]+a[2]));   
        int ans = 0;
        int[] f = new int[n + 10];
        for (int i = 0; i < n; i++) {
            f[i] = cs[i][2];
            for (int j = 0; j < i; j++) {
                if (cs[j][0] >= cs[i][0] && cs[j][1] >= cs[i][1] && cs[j][2] >= cs[i][2]) {
                    f[i] = Math.max(f[i], f[j] + cs[i][2]);
                }
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int maxHeight(vector<vector<int>>& cs) {
        int n = cs.size();
        for(int i = 0; i < n; i++) sort(cs[i].begin(), cs[i].end());
        sort(cs.begin(), cs.end(), [](vector<int>& a, vector<int>& b){
            return a[0] + a[1] + a[2] > b[0] + b[1] + b[2];
        });
        vector<int> f(n + 10, 0);
        int ans = 0;
        for(int i = 0; i < n; i++) {
            f[i] = cs[i][2];
            for(int j = 0; j < i; j++) {
                if(cs[j][0] >= cs[i][0] && cs[j][1] >= cs[i][1] && cs[j][2] >= cs[i][2]) {
                    f[i] = max(f[i], f[j] + cs[i][2]);
                }
            }
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def maxHeight(self, cs):
        n = len(cs)
        for i in range(n):
            cs[i].sort()
        cs.sort(key=lambda x: -(x[0]+x[1]+x[2]))
        f, ans = [0] * (n+10), 0
        for i in range(n):
            f[i] = cs[i][2]
            for j in range(i):
                if cs[j][0] >= cs[i][0] and cs[j][1] >= cs[i][1] and cs[j][2] >= cs[i][2]:
                    f[i] = max(f[i], f[j] + cs[i][2])
            ans = max(ans, f[i])
        return ans

TypeScript 代码：

function maxHeight(cs: number[][]): number {
    const n = cs.length;
    for (let i = 0; i < n; i++) cs[i].sort((a, b) => a-b);
    cs.sort((a, b) => (b[0] + b[1] + b[2]) - (a[0] + a[1] + a[2]));
    const f: number[] = new Array(n + 10).fill(0);
    let ans = 0;
    for (let i = 0; i < n; i++) {
        f[i] = cs[i][2];
        for (let j = 0; j < i; j++) {
            if (cs[j][0] >= cs[i][0] && cs[j][1] >= cs[i][1] && cs[j][2] >= cs[i][2]) {
                f[i] = Math.max(f[i], f[j] + cs[i][2]);
            }
        }
        ans = Math.max(ans, f[i]);
    }
    return ans;
};