UVa 437 The Tower of Babylon

题目描述题目要求用给定的砖块堆砌尽可能高的塔。有nnn种砖块每种砖块无限供应。每个砖块是长方体尺寸为(xi,yi,zi)(x_i, y_i, z_i)(xi​,yi​,zi​)。砖块可以任意旋转即任意一个尺寸可以作为高度另外两个尺寸作为底面边长。堆砌时上方的砖块底面两个边长必须严格小于下方砖块对应的底面边长方向可以旋转匹配。求能堆砌的最大高度。输入格式输入包含多个测试用例。每个测试用例第一行一个整数nnnn≤30n \le 30n≤30表示砖块种类数。接下来nnn行每行三个整数xi,yi,zix_i, y_i, z_ixi​,yi​,zi​。输入以n0n 0n0结束。输出格式对于每个测试用例输出一行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.xi.xj.x i.xj.xi.x且j.yi.yj.y i.yj.yi.y或j.xi.yj.x i.yj.xi.y且j.yi.xj.y i.xj.yi.x。由于边长已按降序排列判断条件简化为j.xi.xj.x i.xj.xi.x且j.yi.yj.y i.yj.yi.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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structblock{intx,y,z;booloperator(constblockanother)const{if(x!another.x)returnxanother.x;if(y!another.y)returnyanother.y;returnzanother.z;}booloperator(constblockanother)const{returnxanother.xyanother.yzanother.z;}};vectorblockblocks;mapint,intmemoization;intn,max_height0;boolsmaller(intlength,intwidth,intnext_length,intnext_width){return(next_lengthlengthnext_widthwidth)||(next_lengthwidthnext_widthlength);}voidbacktrack(intid,intlength,intwidth,intheight){for(inti0;in;i){if(smaller(length,width,blocks[i].x,blocks[i].y)){intnext_idblocks[i].x*1000blocks[i].y;if(memoization[next_id]0){if(heightmemoization[next_id]max_height)max_heightheightmemoization[next_id];if(heightmemoization[next_id]memoization[id])memoization[id]heightmemoization[next_id];}elsebacktrack(id,blocks[i].x,blocks[i].y,heightblocks[i].z);}}if(heightmax_height)max_heightheight;if(heightmemoization[id])memoization[id]height;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0,x,y,z;while(cinn,n){blocks.clear();memoization.clear();for(inti1;in;i){cinxyz;if(xy)swap(x,y);if(xz)swap(x,z);if(yz)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());nunique(blocks.begin(),blocks.end())-blocks.begin();max_height0;for(inti0;in;i)backtrack(blocks[i].x*1000blocks[i].y,blocks[i].x,blocks[i].y,blocks[i].z);coutCase cases: maximum height max_height\n;}return0;}