HDU 1069 Monkey and Banana：長方體疊放 DP 經典題解

題目轉化

每種磚塊 (x,y,z) 可旋轉，得到 3 種底面朝向：

• 底面 (x,y) 高 z
• 底面 (x,z) 高 y
• 底面 (y,z) 高 x

將所有朝向展開，共 3n 種「磚塊型態」。問題轉為：從中選擇序列疊放，上層底面長寬**嚴格小於**下層，最大化總高度。這是**最長遞增子序列 (LIS) 的二維擴展**。

DP 狀態定義

dp[i]：以第 i 型態磚塊作為**頂層**時的最大總高度。

狀態轉移

dp[i] = height[i] + max{ dp[j] | j < i 且 brick[j] 可疊在 brick[i] 下 }

「可疊放」條件：w_j > w_i 且 l_j > l_i (寬長均嚴格大)。為方便比較，預先將每磚塊的 w ≤ l 排序，並按底面積 w*l **降序**排序，保證轉移只從前向後。

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;

struct Block {
    int w, l, h, area;
    bool operator<(const Block& o) const { return area > o.area; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, tc = 1;
    while (cin >> n && n) {
        vector blocks;
        for (int i = 0; i < n; ++i) {
            int x, y, z; cin >> x >> y >> z;
            // 3 種朝向，確保 w <= l
            blocks.push_back({min(x,y), max(x,y), z, x*y});
            blocks.push_back({min(x,z), max(x,z), y, x*z});
            blocks.push_back({min(y,z), max(y,z), x, y*z});
        }
        sort(blocks.begin(), blocks.end());

        int m = blocks.size();
        vector dp(m);
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            dp[i] = blocks[i].h;
            for (int j = 0; j < i; ++j) {
                if (blocks[j].w > blocks[i].w && blocks[j].l > blocks[i].l)
                    dp[i] = max(dp[i], dp[j] + blocks[i].h);
            }
            ans = max(ans, dp[i]);
        }
        cout << "Case " << tc++ << ": maximum height = " << ans << "\n";
    }
    return 0;
}

樣例驗證

輸入:
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0

輸出:
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

關鍵點總結

• 展開 3 個朝向，並統一 w ≤ l，避免重複比較
• 按底面積降序排序，保證 DP 拓撲順序 (大底面在前)
• 嚴格大於 (>) 而非大於等於，題目要求「嚴格較小」
• 時間複雜度 O((3n)²)，n ≤ 30 時 90² = 8100 極快
• 空間優化：可用一維 dp，無需二維