题意：对于给定的n中类型的长方体，怎么样堆起来才能有最大的高度；
约束条件。下面的长方体的上表面要大于上面得下表面，切不能有一条边是长度相同
题目说任意类型的长方体的数量是无限的，其实最多用的到的也就3块
另外假设长方体规格是 a x b x c
if(a==b==c)
then 取axbxc的一块
if(a==b!=c)
then 取 axbxc 一块 取axcxb一块
if(a!=b==c)
同上
其余情况即三边都不相等
取axbxc, axcxb, bxcxa
题目说n最大30，所以数组最大需要3x30
struct Node{ int x, y, z; }aa[100];
对了，上面说到的规格都是大的一边在前的，第三个字母代表高度
剩下的就是排序了，
按照长边降序排序，
如果长边相等，按照短边降序排序
。。。
最后就是求最大值了
#include <cstdio> #include <algorithm> using namespace std; struct Node{ int x, y, z; }aa[100]; int a, b, c; int main(){ int t = 1, i, idx, n, ans, j, tmp; void exchange(); bool cmp(Node p, Node q); while(scanf("%d",&n),n){ ans = -1; for(i = idx = 0; i < n; i++){ scanf("%d%d%d",&a,&b,&c); if(a == b && b == c){ aa[idx].x = aa[idx].y = aa[idx].z = a; if(aa[idx].z > ans) ans = aa[idx].z; idx++; }else{ exchange(); if(a == b){ //1 aa[idx].x = a, aa[idx].y = b, aa[idx].z = c; if(aa[idx].z > ans) ans = aa[idx].z; idx++; //2 aa[idx].x = a, aa[idx].y = c, aa[idx].z = b; if(aa[idx].z > ans) ans = aa[idx].z; idx++; }else if(b == c){ //1 aa[idx].x = a, aa[idx].y = b, aa[idx].z = c; if(aa[idx].z > ans) ans = aa[idx].z; idx++; //2 aa[idx].x = b, aa[idx].y = c, aa[idx].z = a; if(aa[idx].z > ans) ans = aa[idx].z; idx++; }else{ //1 aa[idx].x = a, aa[idx].y = b, aa[idx].z = c; if(aa[idx].z > ans) ans = aa[idx].z; idx++; //2 aa[idx].x = a, aa[idx].y = c, aa[idx].z = b; if(aa[idx].z > ans) ans = aa[idx].z; idx++; //3 aa[idx].x = b, aa[idx].y = c, aa[idx].z = a; if(aa[idx].z > ans) ans = aa[idx].z; idx++; } } } n = idx; sort(aa,aa+n,cmp); for(i = n - 2; i >= 0; i--){ tmp = 0; for(j = i + 1; j < n; j++){ if(aa[j].x < aa[i].x && aa[j].y < aa[i].y){ if(aa[j].z > tmp) tmp = aa[j].z; } } aa[i].z += tmp; if(aa[i].z > ans) ans = aa[i].z; } printf("Case %d: maximum height = %d/n",t++,ans); } return 0; } bool cmp(Node p, Node q){ if(p.x != q.x) return p.x > q.x; if(p.y != q.y) return p.y > q.y; return p.z > q.z; } void exchange(){ int tmp; if(a < b){ tmp = a; a = b; b = tmp; } if(a < c){ tmp = a; a = c; c = tmp; } if(b < c){ tmp = b; b = c; c = tmp; } }
