1691. 堆叠长方体的最大高度

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • LIS
  • 排序
  • 贪心

思路

1. 问题描述（数学化）

给定 \(n\) 个长方体，每个长方体由三条边长表示。允许对每个长方体进行任意旋转，但每个长方体 最多使用一次。 当一个长方体放在另一个长方体上时，要求其在底面的两个方向上不超过下方长方体对应的尺寸。

目标：求能够堆叠得到的最大总高度。

2. 统一表示与旋转的处理

2.1 单个长方体的规范化表示

对任意一个长方体，其三条边长记为 \((x,y,z)\)。 由于允许旋转，三条边本质上是无序的。

将其排序为： \[ (x,y,z)\ \longrightarrow\ (a,b,c), \quad a \le b \le c \] 称 \((a,b,c)\) 为该长方体的规范表示。

  • \(a\)：最短边
  • \(b\)：中间边
  • \(c\)：最长边

该步骤对应代码中的：

1
sort(arr.begin(), arr.end());

2.2 两个长方体能否叠放的判定条件

设两个长方体的规范表示分别为： \[ A = (a_1,a_2,a_3), \quad B = (b_1,b_2,b_3) \] 其中： \[ a_1 \le a_2 \le a_3,\quad b_1 \le b_2 \le b_3 \]

判定条件

A 可以放在 B 上 当且仅当：

\[ a_1 \le b_1,\quad a_2 \le b_2,\quad a_3 \le b_3 \]

下面证明该条件是充分且必要的。

3. 判定条件的数学证明

3.1 充分性证明（Sufficiency）

命题： 若 \[ a_1 \le b_1,\quad a_2 \le b_2,\quad a_3 \le b_3, \] 则存在一种旋转方式，使得长方体 \(A\) 可以放在长方体 \(B\) 上。

证明：

  • 由于三条边均已排序，可将 \(A\) 的最短边对齐 \(B\) 的最短边， 中间边对齐中间边，最长边对齐最长边；
  • 在这种对应关系下，三个方向上的尺寸均不超过 \(B\)；
  • 因此，在该旋转方式下，\(A\) 在空间上完全可以被 \(B\) 承载。

故该条件是充分的。 \(\square\)

3.2 必要性证明（Necessity）

命题： 若长方体 \(A\) 可以通过某种旋转方式放在长方体 \(B\) 上，则必有： \[ a_1 \le b_1,\quad a_2 \le b_2,\quad a_3 \le b_3. \] 证明：

反证法。

  • 假设 \(A\) 可以放在 \(B\) 上，但存在： \[ a_3 > b_3 \]

  • 注意到 \(b_3\) 是 \(B\) 的最大边长，因此 \(B\) 的任意一条边均不超过 \(b_3\)；

  • 而 \(A\) 至少有一条边长度为 \(a_3\)，无论如何旋转，该边都无法匹配到 \(B\) 的任何一条边上；

  • 这与“\(A\) 可以放在 \(B\) 上”的假设矛盾。

同理，若 \(a_2 > b_2\) 或 \(a_1 > b_1\)，也会导致至少一条边无法被容纳。

因此必须有： \[ a_1 \le b_1,\quad a_2 \le b_2,\quad a_3 \le b_3. \] 故该条件是必要的。 \(\square\)

3.3 结论

\[ A \text{ 可以放在 } B \text{ 上} \quad\Longleftrightarrow\quad (a_1,a_2,a_3) \le (b_1,b_2,b_3)\ \text{（逐维）} \]

这是后续动态规划建模的理论基础。

4. 动态规划建模

4.1 全局排序与 DAG 结构

将所有长方体按其规范表示 \((a,b,c)\) 字典序排序： \[ (a,b,c) \uparrow \] 排序后具有如下性质：

若长方体 \(j\) 可以放在长方体 \(i\) 上，则必有 \(j < i\)。

因此，堆叠关系天然构成一张有向无环图（DAG）。

4.2 状态定义

定义： \[ f[i] = \text{以第 } i \text{ 个长方体作为最底层时的最大总高度} \] 由于在规范表示中，最长边 \(c\) 一定可以作为高度贡献，因此： \[ f[i] \ge c_i \]

4.3 状态转移方程

对所有 \(j < i\)，若： \[ a_j \le a_i,\quad b_j \le b_i,\quad c_j \le c_i \] 则第 \(j\) 个长方体可以放在第 \(i\) 个之上，有转移： \[ f[i] = \max\bigl(f[i],\ f[j] + c_i\bigr) \]

4.4 初始化与答案

  • 初始化：

\[ f[i] = c_i \]

  • 最终答案：

\[ \max_{1 \le i \le n} f[i] \]

5. 算法复杂度分析

  • 排序复杂度：\(O(n\log n)\)
  • 动态规划转移：\(O(n^2)\)
  • 总时间复杂度：

\[ O(n^2) \]

在 \(n \le 100\) 的约束下完全可行。

  • 空间复杂度：\(O(n)\)

6. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static const int maxn = 1e2 + 5;
    int maxHeight(vector<vector<int>>& cuboids) {
        for (auto& arr : cuboids)
            sort(arr.begin(), arr.end());
        sort(cuboids.begin(), cuboids.end());
        int f[maxn], n = cuboids.size();
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            int l = cuboids[i - 1][0], w = cuboids[i - 1][1],
                h = cuboids[i - 1][2];
            f[i] = h;
            for (int j = i - 1; j >= 1; --j) {
                if (l >= cuboids[j - 1][0] && w >= cuboids[j - 1][1] &&
                    h >= cuboids[j - 1][2])
                    f[i] = max(f[i], f[j] + h);
            }
            res = max(res, f[i]);
        }
        return res;
    }
};