1098 - 猴子与香蕉
一组研究人员正在设计一个测试猴子IQ的实验。他们把香蕉吊在屋顶上，同时给猴子提供了砖块。如果猴子够聪明，它会把砖块一个个叠起来做成一个塔，然后爬上去拿到自己喜爱的食物。
研究人员有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
C语言解答
#include "stdio.h" void rank(int *x,int *y,int *z) { int t; if(*x>*y) t=*x,*x=*y,*y=t; if(*y>*z) t=*z,*z=*y,*y=t; if(*x>*y) t=*x,*x=*y,*y=t; } int main() { int n; int a[100],b[100],h[100]; int H[100],max; int x,y,z; int i,j; int t; int m; scanf("%d",&n); m=1; while(n) { j=1; for(i=0;i<n;i++) { scanf("%d%d%d",&x,&y,&z); rank(&x,&y,&z); a[j]=x,b[j]=y,h[j]=z; j++; a[j]=y,b[j]=z,h[j]=x; j++; a[j]=x,b[j]=z,h[j]=y; j++; } n=j-1; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) if(a[i]<a[j]) { t=a[i],a[i]=a[j],a[j]=t; t=b[i],b[i]=b[j],b[j]=t; t=h[i],h[i]=h[j],h[j]=t; } } memset(H,0,sizeof(H)); for(i=1;i<=n;i++) { max=0; for(j=i-1;j>0;j--) if(a[i]<a[j]&&b[i]<b[j]&&max<H[j]) max=H[j]; H[i]=h[i]+max; } max=0; for(i=1;i<=n;i++) if(max<H[i]) max=H[i]; printf("Case %d: maximum height = %d\n",m,max); scanf("%d",&n); m++; } return 0; }
C++解答
#include<cstdio> #include<algorithm> using namespace std; struct BOX { int x,y,z; }box[180]; void f(int k,int x,int y,int z) { box[k].x=x; box[k].y=y; box[k].z=z; } bool cmp(BOX a,BOX b) { return a.x>b.x; } int main() { int n,i,j,x,y,z,k,h[180],maxi,ans,c=0; while(scanf("%d",&n)!=EOF,n) { for(k=i=0;i<n;i++) { scanf("%d%d%d",&x,&y,&z); f(k++,x,y,z); f(k++,y,x,z); f(k++,x,z,y); f(k++,z,x,y); f(k++,y,z,x); f(k++,z,y,x); } n*=6; sort(box,box+n,cmp); for(i=0;i<n;i++) h[i]=box[i].z; for(ans=i=0;i<n;i++) { for(maxi=0,j=i-1;j>=0;j--) if(box[i].x<box[j].x&&box[i].y<box[j].y&&maxi<h[j]) maxi=h[j]; h[i]+=maxi; if(ans<h[i]) ans=h[i]; } printf("Case %d: maximum height = %d\n",++c,ans); } return 0; }