ZOJ 1093 Monkey and Banana：磚塊疊放最長路徑 DP（盒子嵌套變體）

題目大意

n ≤ 30 種磚塊，每種給長寬高 (x, y, z)，無限供應。磚塊可旋轉（長寬互換），嚴格小的長寬可疊在大的上面。求最大堆疊高度。

關鍵轉化：每種磚產生 3 種朝向

對每組 (x, y, z)，取兩個較大維度作底面長寬（a ≥ b），最小作高 c。三種朝向：
(a, b, c), (a, c, b), (b, c, a)。
共 3n 塊「定向磚」，每塊用 (底長, 底寬, 高) 表示，且 底長 ≥ 底寬。

DP：按底面面積/長寬排序求最長路徑

• 排序：底長降序，底長同則底寬降序。保證若 i < j，則磚 i 可墊在 j 下面（或不可比）。
• dp[i] = 以磚 i 為頂的最大高度。
  dp[i] = height[i] + max{ dp[j] | j < i 且 brick[j].長 > brick[i].長 且 brick[j].寬 > brick[i].寬 }
• 雙重迴路 O((3n)²) = O(n²)，n=30 瞬時完成。

參考代碼邏輯

for i in 0..3n-1:
    dp[i] = brick[i].h
    for j in 0..i-1:
        if brick[j].x > brick[i].x && brick[j].y > brick[i].y
            dp[i] = max(dp[i], dp[j] + brick[i].h)
ans = max(dp)

輸出格式

Case %d: maximum height = %d，測資編號從 1 開始。

總結

本題是經典「盒子嵌套 / 磚塊疊放」DP 的簡化版（無限供應、僅比較長寬）。核心步驟：展開旋轉朝向 → 排序消除無效前驅 → O(N²) DP 求加權最長路徑。代碼簡潔，邏輯清晰，是 DP 入門佳例。