thetowerofbabyon.cpp

The Tower of Babylon acm 题解

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int x,y,z;
	int area;
}box[93];
struct node1 
{
    int h;
}best[93];
int a[3]={0};
int cmp(const void *a,const void *b)
{
    return (*(node*)b).area>(*(node*)a).area;
}
int main()
{
	int n,i,j,k,count,ans,t=0;
	while(scanf("%d",&n)&&n)
	{
		t++;
		count=0;
		ans=0;
        for(i=0;i<n;i++)
        {
		    scanf("%d%d%d",&a[0],&a[1],&a[2]);
		    for(k=0;k<3;k++)
		    {
                box[count].x=a[k%3];
                box[count].y=a[(k+1)%3];
                box[count].z=a[(k+2)%3];
                box[count].area=box[count].x*box[count].y;
                count++;
            }
        }
        qsort(box,count,sizeof(box[0]),cmp);
		for(i=0;i<count;i++)
			best[i].h=box[i].z;
        for(i=1;i<count;i++)
		{
            for(j=0;j<i;j++)
			{
				if(((box[i].x<box[j].x&&box[i].y<box[j].y)||(box[i].x<box[j].y&&box[i].y<box[j].x))&&((best[j].h+box[i].z)>best[i].h))
					best[i].h=best[j].h+box[i].z;
            }
        }
        for(i=0;i<count;i++)
			if(ans<best[i].h)	ans=best[i].h;
		printf("Case %d: maximum height = %d\n",t,ans);
    }
    return 0;
}