您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

HDU 1069 Monkey and Banana：磚塊疊塔求最大高度（LIS 變體 + 狀態展開）

編輯：關於C語言

HDU 1069 Monkey and Banana：磚塊疊塔求最大高度（LIS 變體 + 狀態展開）

經典動態規劃問題：給定 n 種磚塊（每種無限供應），每塊長寬高可任意旋轉（6 種朝向），上層磚塊長寬必嚴格小於下層，求最大疊塔高度。本文詳細講解「狀態展開 + 排序 + DP」標準解法，並提供優化代碼模板。

問題建模

每種磚塊 (x, y, z) 可旋轉為 6 種 (長, 寬, 高) 三元組，約定 長 ≥ 寬 去重，實際 3 種有效朝向：
(max, mid, min)、(max, min, mid)、(mid, min, max)。
疊放條件：上層長 < 下層長且上層寬 < 下層寬。
目標：選擇一個朝向序列，滿足遞減條件，最大化總高度和。

核心思路：最長遞減子序列 (LDS) 變體

狀態展開：將 n 種磚塊展開為 3n 個「磚塊實例」，每個實例包含 (長, 寬, 高)。
排序：按長遞減、長相同則按寬遞減排序。排序後，合法疊放只能從前向後（下層在前，上層在後）。
DP 定義：dp[i] 表示以第 i 個實例作為塔底（最下層）時的最大高度。
轉移：對每個 i，遍歷 j > i（潛在上層），若 a[i].l > a[j].l && a[i].w > a[j].w，則 dp[i] = max(dp[i], a[i].h + dp[j])。
答案：max(dp[i])。

完整代碼（C++，AC 模板）

#include 
using namespace std;

struct Brick {
    int l, w, h; // 長 ≥ 寬
};

bool cmp(const Brick &a, const Brick &b) {
    if (a.l != b.l) return a.l > b.l; // 長遞減
    return a.w > b.w;                 // 寬遞減
}

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

    int n, tc = 1;
    while (cin >> n && n) {
        vector a;
        a.reserve(n * 3);
        for (int i = 0; i < n; ++i) {
            int x, y, z;
            cin >> x >> y >> z;
            int b[3] = {x, y, z};
            sort(b, b + 3); // b[0] ≤ b[1] ≤ b[2]
            // 3 種有效朝向：長≥寬
            a.push_back({b[2], b[1], b[0]}); // 最大作長，中作寬，最小作高
            a.push_back({b[2], b[0], b[1]}); // 最大作長，最小作寬，中作高
            a.push_back({b[1], b[0], b[2]}); // 中作長，最小作寬，最大作高
        }

        sort(a.begin(), a.end(), cmp);
        int m = a.size();
        vector dp(m);
        for (int i = 0; i < m; ++i) dp[i] = a[i].h; // 初始：自身高度

        // 從後向前 DP：i 為塔底，尋找可放在其上的 j
        for (int i = m - 2; i >= 0; --i) {
            for (int j = i + 1; j < m; ++j) {
                if (a[i].l > a[j].l && a[i].w > a[j].w) {
                    dp[i] = max(dp[i], a[i].h + dp[j]);
                }
            }
        }

        int ans = *max_element(dp.begin(), dp.end());
        cout << "Case " << tc++ << ": maximum height = " << ans << '\n';
    }
    return 0;
}

關鍵細節解析

環節	細節	理由
去重朝向	長≥寬，僅保留 3 種	6 種旋轉中 (l,w) 與 (w,l) 等價，固定長≥寬消除對稱性
排序順序	長遞減、寬遞減	保證下層在前，上層在後，DP 單向轉移無環
DP 方向	從後向前（塔底→塔頂）	塔底依賴上層結果，逆序計算 dp[j] 已知
初始值	dp[i] = a[i].h	至少可單獨作為塔
嚴格小於	l > l' && w > w'	題目要求「留空間給猴子踩」，不可等於