ZeroJudge 解題筆記：c115. 00437 - The Tower of Babylon

作者：王一哲
日期：2026年3月11日


ZeroJudge 題目連結：c115. 00437 - The Tower of Babylon

解題想法

因為方塊可以旋轉，在讀取方塊邊長時，先將邊長排序，假設邊長依序為 $x, y, z$，將三種邊長排列方式都存入串列 blocks 之中。接下來將 blocks 依照長、寬由大到小排序，用 dp 計算最大高度。

Python 程式碼

使用時間約為 16 ms，記憶體約為 3 MB，通過測試。

import sys

ca = 0
result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)  # 積木數量
    if n == 0: break  # 中止迴圈條件
    ca += 1
    blocks = []  # 可能的積木尺寸
    for _ in range(n):  # 讀取 n 行資料
        x, y, z = sorted(map(int, sys.stdin.readline().split()))  # x >= y >= z
        blocks.append((z, y, x))  # 取長、寬較大者放前面
        blocks.append((z, x, y))
        blocks.append((y, x, z))
    blocks.sort(key = lambda b : (b[0], b[1]), reverse=True)  # 依照長、寬由大到小排序
    m = len(blocks)  # 可用的積木數量
    dp = [0]*m  # 以第 i 塊為最上方的積木，累計的最大高度
    for i in range(m):  # 依序掃過第 0 ~ m-1 塊積木
        xi, yi, zi = blocks[i]  # 第 i 塊的 x、y、z 大小
        dp[i] = zi  # 如果只放第 i 塊，高度為 zi
        for j in range(i):  # 依序掃過第 0 ~ i-1 塊積木
            xj, yj = blocks[j][0], blocks[j][1]
            if xj > xi and yj > yi:  # 第 i 塊可以放在第 j 塊上面
                dp[i] = max(dp[i], dp[j] + zi)  # 取第 i 塊目前的高度、第 j 塊的高度加上 zi 較大者
    result.append(f"Case {ca:d}: maximum height = {max(dp):d}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 316 kB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int ca = 0, n;
    while(scanf("%d", &n) != EOF && n != 0) {
        ca++;
        vector<vector<int>> blocks;
        for(int i=0; i<n; i++) {
            vector<int> block (3);
            for(int j=0; j<3; j++) scanf("%d", &block[j]);
            sort(block.begin(), block.end());
            blocks.push_back({block[2], block[1], block[0]});
            blocks.push_back({block[2], block[0], block[1]});
            blocks.push_back({block[1], block[0], block[2]});
        }
        sort(blocks.begin(), blocks.end(), greater<vector<int>> ());
        int m = (int)blocks.size();
        vector<int> dp (m, 0);
        for(int i=0; i<m; i++) {
            int xi = blocks[i][0], yi = blocks[i][1], zi = blocks[i][2];
            dp[i] = zi;
            for(int j=0; j<i; j++) {
                int xj = blocks[j][0], yj = blocks[j][1];
                if (xj > xi && yj > yi) {
                    dp[i] = max(dp[i], dp[j]+zi);
                }
            }
        }
        int imax = *max_element(dp.begin(), dp.end());
        printf("Case %d: maximum height = %d\n", ca, imax);
    }
    return 0;
}