描述
一组研究人员正在设计一个测试猴子智商的实验。他们会在建筑物的屋顶上挂一根香蕉，同时给猴子一些块。如果猴子够聪明，就可以通过在顶部放一个块来建立一个塔，爬上去获得最喜欢的食物，到达香蕉。
研究人员有n种类型的块，并且每种类型的块都是无限制的。每个i型块是具有线性尺寸（xi，yi，zi）的矩形固体。块可以重新定向，使得其三维中的任何两个尺寸确定基部的尺寸，而另一个尺寸确定为高度。
他们想确保最高的塔可能通过堆叠块可以到达屋顶。问题在于，在建造塔楼时，一个块只能放置在另一块的顶部，只要上块的两个基本尺寸都严格小于下块的相应基座尺寸，因为必须有一些空间可供猴子踩踏。这意味着，例如，面向具有相等大小的基座的块不能被堆叠。
你的工作是编写一个程序，用来确定猴子可以用一组给定的块建立的最高塔的高度。
输入
输入文件将包含一个或多个测试用例。每个测试用例的第一行包含一个整数n，
表示以下数据集中不同块的数量。n的最大值为30.
接下来的n行中的每一行包含表示值xi，yi和zi的三个整数。
n的值为零（0）终止输入。
输出
对于每个测试用例，打印一行包含案例编号（它们从1开始按顺序编号）和最高可能的塔的高度，格式为“Case case：maximum height = height”。
类似于最长上升子序列问题，不过有几个要注意的点。
1. 一个长方体最多可以有3个不同的底面，所以一个块最多可以用三次。
2. 最长上升子序列要求下标是递增的，但在这里，高度最高的塔使用的块的下标在数组中并不一定是递增的，在 dp 之前使用排序可以解决这个问题（具体写在代码注释里了）。 （╮(╯▽╰)╭ 这里愣了好久，真是越来越笨了）
代码：
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int MAX = 3*35; struct Node{ int x, y, z; }; int n; int dp[MAX]; Node node[MAX]; bool cmp(Node a, Node b){ return a.x * a.y > b.x * b.y; } int main(){ //freopen("input.txt", "r", stdin); int T = 0; while(cin >> n && n != 0){ for(int i=1; i<=3*n; i++){ cin >> node[i].x >> node[i].y >> node[i].z; node[i+1].x = node[i].y; //将块旋转， 一共可获得三种块 node[i+1].y = node[i].z; node[i+1].z = node[i].x; node[i+2].x = node[i].x; node[i+2].y = node[i].z; node[i+2].z = node[i].y; i += 2; } //按照面积从大到小排序，则前面的一定不可能放在后面的块上， //即当前块为顶的塔的最大高度与后面的块无关。 sort(node + 1, node + 1 + 3*n, cmp); dp[0] = 0; int maxH = 0; for(int i=1; i<=3*n; i++){ dp[i] = node[i].z; for(int j=1; j<i; j++){ if(node[i].x < node[j].x && node[i].y < node[j].y || node[i].x < node[j].y && node[i].y < node[j].x){ dp[i] = max(dp[i], dp[j] + node[i].z); } } maxH = max(maxH, dp[i]); } cout << "Case " << ++T << ": maximum height = " << maxH << endl; } }