问题描述：
有一班科学家正在设计一个测试猴子IQ的试验。他们 把一只“banana”吊在天花板，而且同时给猴子一些箱子。如果猴子聪明的话，它们会把箱子一个个叠起来做成一个塔子来取得食物。科学家有n种箱子，而且每一种箱子都有好多个。第 i 种箱子有三维（xi,yi,zi)。箱子可以用它的任意一面作底面来摆放，也就是它的三维之中可以任选两条来做它的底面长和宽。科学家想确定箱子叠到最高的时候是可以到达天花板的。现在问题是，要叠起一个塔子，上下摆放的两个箱子，在上的箱子的底面长宽必须严格小于在下的箱子的底面长宽,留下些地方让猴子落脚来爬上去。也就是说，底面面积相等的箱子不能叠放。现在你的任务是利用所给定的箱子，决定塔子最高能达到的高度

输入：
输入数据有多组测试数据。
每一组测试数据的第一行是一个整数n，表示不同三维的箱子的总数。n最大为30。
以下的n行每一行有三个正整数，表示该箱子的三维xi,yi和zi。
当n=0的时候输入结束。

输出：
对应每组测试数据，输出一行包括数据组号case（从1开始）和塔子最高高度height，
并按照一下格式： "Case case: maximum height = 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

// DP

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 32
#define SWAP(a,t,b) { t=a; a=b; b=t; }

typedef struct node{
 int length;
 int width;
 int height;
 int value;
}NODE;

void deal(int *a,int *b,int *c){
 int t;
 if(*a > *b)
  SWAP(*a,t,*b);
 if(*a > *c)
  SWAP(*a,t,*c);
 if(*b > *c)
  SWAP(*b,t,*c);
}

void copy(int a,int b,int c,NODE *p){
 p->length = a;
 p->width = b;
 p->value = p->height = c;
}

int myCmp(const NODE *a,const NODE *b){
 if(a->length>b->length||(a->length==b->length && a->width>b->width))
  return 1;
 if(a->length==b->length && a->width==b->width)
  return 0;
 return -1;
}

void get(int *rlt, NODE *d, int i, int j){
 int m,r,max;
 for(m=0,max=0; m < i; m++){
  if(d[i].length>d[m].length&&d[i].width>d[m].width&&d[m].value>max){
   r = m;
   max = d[m].value;
  }
 }
 d[i].value += max;
 *rlt = (*rlt > d[i].value ? *rlt : d[i].value);
}

int main(){
 int  rlt,i,j,a,b,c,n,m=0;
 NODE d[MAX*3];
 for(m=1; scanf("%d",&n)!=EOF && n; m++){
  memset(d,0,sizeof(NODE)*MAX*3);
  for(j=i=0; i < n; i++){
   scanf("%d %d %d",&a,&b,&c);
   deal(&a,&b,&c);
   copy(a,b,c,&d[j++]);
   if(b != c)
    copy(a,c,b,&d[j++]);
   if(a != b)
    copy(b,c,a,&d[j++]);
  }
  qsort(d,j,sizeof(NODE),myCmp);
  for(rlt=d[0].value,i=1; i < j; i++)
   get(&rlt,d,i,j);
  printf("Case %d: maximum height = %d\n",m,rlt);
 }
 return 0;
}

评论