问题描述：有一班科学家正在设计一个测试猴子IQ的试验。他们 把一只“banana”吊在天花板，而且同时给猴子一些箱子。如果猴子聪明的话，它们会把箱子一个个叠起来做成一个塔子来取得食物。科学家有n种箱子，而且每一种箱子都有好多个。第 i 种箱子有三维（xi,yi,zi)。箱子可以用它的任意一面作底面来摆放，也就是它的三维之中可以任选两条来做它的底面长和宽。科学家想确定箱子叠到最高的时候是可以到达天花板的。现在问题是，要叠起一个塔子，上下摆放的两个箱子，在上的箱子的底面长宽必须严格小于在下的箱子的底面长宽,留下些地方让猴子落脚来爬上去。也就是说，底面面积相等的箱子不能叠放。现在你的任务是利用所给定的箱子，决定塔子最高能达到的高度 输入：输入数据有多组测试数据。每一组测试数据的第一行是一个整数n，表示不同三维的箱子的总数。n最大为30。以下的n行每一行有三个正整数，表示该箱子的三维xi,yi和zi。当n=0的时候输入结束。 输出：对应每组测试数据，输出一行包括数据组号case（从1开始）和塔子最高高度height，并按照一下格式： "Case case: maximum height = height" 样例输入110 20 3026 8 105 5 571 1 12 2 23 3 34 4 45 5 56 6 67 7 7531 41 5926 53 5897 93 2384 62 6433 83 270 样例输出Case 1: maximum height = 40Case 2: maximum height = 21Case 3: maximum height = 28Case 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;}

评论