解题思路

1. 问题转化

由于积木可以旋转，我们需要枚举每个积木的所有可能摆放方式。对于一个尺寸为 (x, y, z) 的积木，可以有以下 6 种摆放方式（3 种底面 × 2 种高度方向）：

1. (x, y, z)（底面 x × y，高度 z）
2. (x, z, y)（底面 x × z，高度 y）
3. (y, x, z)（底面 y × x，高度 z）
4. (y, z, x)（底面 y × z，高度 x）
5. (z, x, y)（底面 z × x，高度 y）
6. (z, y, x)（底面 z × y，高度 x）

2. 排序优化

为了便于动态规划计算，我们需要对所有可能的积木块进行排序：

• 按长 x 降序排序，如果 x 相同，则按 y 降序排序。
• 这样，在动态规划时，可以确保较大的积木先处理，避免重复计算。

3. 动态规划

定义 dp[i] 表示以第 i 个积木为顶时的最大高度。状态转移方程为： [ dp[i] = \text{max}(dp[j] + \text{height}_i) \quad \text{其中} \quad x_j > x_i \quad \text{且} \quad y_j > y_i ] 即，遍历所有 j < i 的积木，找到可以放在 i 下面的积木 j，并更新 dp[i]。

4. 最终答案

最终答案就是所有 dp[i] 中的最大值。

C++实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Block {
    int x, y, z;
    Block(int a, int b, int c) : x(a), y(b), z(c) {}
    bool operator<(const Block& other) const {
        if (x != other.x) return x > other.x; // 按 x 降序
        return y > other.y; // x 相同时按 y 降序
    }
};

int main() {
    int n, caseNum = 0;
    while (cin >> n && n != 0) {
        caseNum++;
        vector<Block> blocks;

        // 生成所有可能的积木摆放方式（6种）
        for (int i = 0; i < n; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            blocks.push_back(Block(x, y, z));
            blocks.push_back(Block(x, z, y));
            blocks.push_back(Block(y, x, z));
            blocks.push_back(Block(y, z, x));
            blocks.push_back(Block(z, x, y));
            blocks.push_back(Block(z, y, x));
        }

        // 按 x 和 y 降序排序
        sort(blocks.begin(), blocks.end());

        // DP: dp[i] 表示以第 i 个积木为顶的最大高度
        vector<int> dp(blocks.size());
        int maxHeight = 0;

        for (int i = 0; i < blocks.size(); i++) {
            dp[i] = blocks[i].z; // 初始高度是当前积木的高度
            for (int j = 0; j < i; j++) {
                if (blocks[j].x > blocks[i].x && blocks[j].y > blocks[i].y) {
                    dp[i] = max(dp[i], dp[j] + blocks[i].z);
                }
            }
            maxHeight = max(maxHeight, dp[i]);
        }

        cout << "Case " << caseNum << ": maximum height = " << maxHeight << endl;
    }
    return 0;
}