题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=93
一堆科学家研究猩猩的智商，给他M种长方体，每种N个。
然后，将一个香蕉挂在屋顶，让猩猩通过 叠长方体来够到香蕉。
现在给你M种长方体，计算，最高能堆多高。
要求位于上面的长方体的长要大于（注意不是大于等于）下面长方体的长，上面长方体的宽大于下面长方体的宽。
解题：
1、一个长方体，可以有6种不同的摆法。长宽排序，就可以只存下来三种，需要的是高的唯一性。
2、将所有长方体按底面积升序排序。
3、第 i 个长方体的最大值 = 前i个（0到i - 1）长方体所能构成的最大高度 + 自己的高度。（升序是为了保证前 i 个长方体底面积一定≤第 i 个，是有可能摆在第i个上面的。）
转移方程：
4、遍历一遍dp数组，得到最大值。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
class block {
public:
int length, width, height;
block() {};
block(int x, int y, int z) {
length = x; width = y; height = z;
}
//按底面积大小升序排序
bool operator <(block b) const {
return length * width < b.width* b.length;
}
}cube[];
];
bool check(block under, block upper) {
if (under.length > upper.length && under.width > upper.width) return true;
return false;
}
int main() {
;
while (cin >> n) {
)break;
; i < n; i++) {
int l, w, h;
scanf("%d%d%d", &l, &w, &h);
//长方体的height,length,width分别作高
cube[i * + ] = block(l > w ? l : w, l > w ? w : l, h);
cube[i * + ] = block(w > h ? w : h, w > h ? h : w, l);
cube[i * + ] = block(h > l ? h : l, l > h ? h : l, w);
}
sort(cube, cube + n * );
dp[] = cube[].height;
; i < n * ; i++) {
;
; j < i; j++) {
if (cube[i].length > cube[j].length && cube[i].width > cube[j].width) {
temp = dp[j] > temp ? dp[j] : temp;//找前i个长方体的最大值
}
}
dp[i] = cube[i].height + temp;
}
;
; i < n * ; i++) {
max = dp[i] > max ? dp[i] : max;
}
cout << "Case " << k++ << ": maximum height = " << max << endl;
}
;
}