每个方块都有3种不同的放置方法，将3种放置方法都存储在数组中，变为底面确定的3个方块。
将所有方块按照最大底面边长从大到小排序，使用动态规划算法，计算最大高度。
#include <iostream> #include <algorithm> using namespace std; struct node //方块 { int x; int y; int z; }; bool cmp(node n1, node n2) //排序规则 { if (n1.x != n2.x) return n1.x > n2.x; else return n1.y > n2.y; } int main() { int n; int icase = 0; //组数 node arr[100]; //方块数组 int dp[100]; //动态规划数组，dp[i]存储的是排序后前i个方块组合的最大高度 while (cin >> n) { if (n == 0) break; int i = 0; int x, y, z; //将每个方块的3个面各做1次底面，即一个方块转换成3种形态 for (int j = 0; j < n; j++) { cin >> x >> y >> z; arr[i].x = max(x, y); arr[i].y = min(x, y); arr[i].z = z; arr[i + 1].x = max(x, z); arr[i + 1].y = min(x, z); arr[i + 1].z = y; arr[i + 2].x = max(y, z); arr[i + 2].y = min(y, z); arr[i + 2].z = x; i += 3; } n = i; //更新n，变为初始n的3倍 sort(arr, arr + n, cmp); //排序 int result = 0; //最终结果 for (int i = 0; i < n; i++) //动态规划 { dp[i] = arr[i].z; for (int j = i - 1; j >= 0; j--) { //下面方块底面边长严格大于上面方块 if (arr[j].x > arr[i].x && arr[j].y > arr[i].y) { if (dp[j] + arr[i].z > dp[i]) dp[i] = dp[j] + arr[i].z; } } if (dp[i] > result) result = dp[i]; } cout << "Case " << ++icase << ": maximum height = " << result << endl; } return 0; }继续加油。
