题目描述
题目要求用给定的砖块堆砌尽可能高的塔。有nnn种砖块，每种砖块无限供应。每个砖块是长方体，尺寸为(xi,yi,zi)(x_i, y_i, z_i)(xi,yi,zi)。砖块可以任意旋转，即任意一个尺寸可以作为高度，另外两个尺寸作为底面边长。堆砌时，上方的砖块底面两个边长必须严格小于下方砖块对应的底面边长（方向可以旋转匹配）。求能堆砌的最大高度。
输入格式
输入包含多个测试用例。每个测试用例：
- 第一行一个整数nnn（n≤30n \le 30n≤30），表示砖块种类数。
- 接下来nnn行，每行三个整数xi,yi,zix_i, y_i, z_ixi,yi,zi。
- 输入以n=0n = 0n=0结束。
输出格式
对于每个测试用例，输出一行：
Case case: maximum height = height其中case为测试用例编号（从111开始），height为最大高度。
样例
输入
1 10 20 30 2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 0输出
Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342题目分析
本题是经典的“巴比伦塔”问题，本质上是一个带约束的最长路径问题（或有向无环图上的最长路）。
状态表示
由于砖块可以旋转，每种砖块最多可以产生666种不同的放置方式（三个尺寸分别作为高度，剩下两个尺寸作为底面边长，且底面边长可交换顺序）。但注意，底面边长本身无序，因此实际上每种砖块有333种不同的高度选择（每个尺寸作为高度），每种高度对应一对底面边长。为了简化后续比较，约定每个状态的底面边长满足x≥yx \ge yx≥y（即底面的较长边在前）。
因此，每种砖块可以生成333个有效状态：
- 以zzz为高度，底面为(x,y)(x, y)(x,y)
- 以yyy为高度，底面为(x,z)(x, z)(x,z)
- 以xxx为高度，底面为(y,z)(y, z)(y,z)
（这里假设x≥y≥zx \ge y \ge zx≥y≥z排序后）
问题转化
将每个状态视为一个节点，节点权值为该状态的高度。若状态uuu的底面能放在状态vvv的底面之上（即uuu的两个底面边长均严格小于vvv对应的边长），则在uuu和vvv之间连一条有向边u→vu \to vu→v（表示vvv可以放在uuu下面）。问题转化为求这个有向无环图（DAG\texttt{DAG}DAG）中的最长路径（节点权值和）。由于每种砖块无限供应，但状态总数有限（最多3n≤903n \le 903n≤90），且相同状态可重复使用（但直接使用会形成环？实际上相同状态叠放会违反边长严格递减，因此图是无环的）。
动态规划
设dp[i]\textit{dp}[i]dp[i]表示以状态iii为顶部的塔的最大高度。状态转移：
dp[i]=height[i]+max{dp[j]∣状态 j 可以放在状态 i 下面} \textit{dp}[i] = \textit{height}[i] + \max\{\textit{dp}[j] \mid \text{状态 } j \text{ 可以放在状态 } i \text{ 下面}\}dp[i]=height[i]+max{dp[j]∣状态j可以放在状态i下面}
其中“可以放在下面”意味着状态jjj的底面两个边长均严格大于状态iii的对应边长（方向可匹配，即j.x>i.xj.x > i.xj.x>i.x且j.y>i.yj.y > i.yj.y>i.y，或j.x>i.yj.x > i.yj.x>i.y且j.y>i.xj.y > i.xj.y>i.x）。
由于边长已按降序排列，判断条件简化为j.x>i.xj.x > i.xj.x>i.x且j.y>i.yj.y > i.yj.y>i.y。
按底面边长排序后，可以从前向后进行动态规划。
实现细节
- 将每个状态存储为(x,y,h)(x, y, h)(x,y,h)，其中x≥yx \ge yx≥y。
- 将所有状态按xxx降序（或升序）排序，以便保证转移方向。
- 使用记忆化搜索或递推计算每个状态的最大高度。
- 最终答案为所有dp[i]\textit{dp}[i]dp[i]的最大值。
复杂度分析
状态数S≤90S \le 90S≤90，转移O(S2)O(S^2)O(S2)，完全可接受。
代码实现
// The Tower of Babylon// UVa ID: 437// Verdict: Accepted// Submission Date: 2016-07-20// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structblock{intx,y,z;booloperator<(constblock&another)const{if(x!=another.x)returnx<another.x;if(y!=another.y)returny<another.y;returnz<another.z;}booloperator==(constblock&another)const{returnx==another.x&&y==another.y&&z==another.z;}};vector<block>blocks;map<int,int>memoization;intn,max_height=0;boolsmaller(intlength,intwidth,intnext_length,intnext_width){return(next_length<length&&next_width<width)||(next_length<width&&next_width<length);}voidbacktrack(intid,intlength,intwidth,intheight){for(inti=0;i<n;i++){if(smaller(length,width,blocks[i].x,blocks[i].y)){intnext_id=blocks[i].x*1000+blocks[i].y;if(memoization[next_id]>0){if(height+memoization[next_id]>max_height)max_height=height+memoization[next_id];if(height+memoization[next_id]>memoization[id])memoization[id]=height+memoization[next_id];}elsebacktrack(id,blocks[i].x,blocks[i].y,height+blocks[i].z);}}if(height>max_height)max_height=height;if(height>memoization[id])memoization[id]=height;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0,x,y,z;while(cin>>n,n){blocks.clear();memoization.clear();for(inti=1;i<=n;i++){cin>>x>>y>>z;if(x<y)swap(x,y);if(x<z)swap(x,z);if(y<z)swap(y,z);blocks.push_back((block){x,y,z});blocks.push_back((block){x,z,y});blocks.push_back((block){y,z,x});}sort(blocks.begin(),blocks.end());n=unique(blocks.begin(),blocks.end())-blocks.begin();max_height=0;for(inti=0;i<n;i++)backtrack(blocks[i].x*1000+blocks[i].y,blocks[i].x,blocks[i].y,blocks[i].z);cout<<"Case "<<++cases<<": maximum height = "<<max_height<<'\n';}return0;}
