Posted on 2012-03-23 10:37
C小加 阅读(407)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
题意：把给定尺寸的长方体（数量不限）叠加在一起，叠加的条件是，上面一个长方体的长和宽比下面长方体的长和宽短，不能相等，长方体可以任意面朝下摆放，求这些长方体能叠加的最高的高度。
把每个长方体分成3个元素。然后就和矩形嵌套差不多了，排序之后求容量最大的子序列。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef
struct {
int l,w,h;
}Cub;
Cub cub[31*3];
int n;
int cnt;
int f[31*3];
bool cmp(Cub c1,Cub c2)
{
if(c1.l==c2.l)
return c1.w<c2.w;
return c1.l<c2.l;
}
bool input()
{
scanf("%d",&n);
if(!n)
return false;
cnt=0;
int l,w,h;
for(
int i=0;i<n;i++)
{
scanf("%d %d %d",&l,&w,&h);
cub[cnt].h=l;
cub[cnt].w=w>h?h:w;
cub[cnt].l=w>h?w:h;
cnt++;
cub[cnt].h=w;
cub[cnt].w=l>h?h:l;
cub[cnt].l=l>h?l:h;
cnt++;
cub[cnt].h=h;
cub[cnt].w=l>w?w:l;
cub[cnt].l=l>w?l:w;
cnt++;
}
return true;
}
void DP()
{
memset(f,0,
sizeof(f));
for(
int i=0;i<cnt;i++) f[i]=cub[i].h;
for(
int i=1;i<cnt;i++)
{
for(
int j=0;j<i;j++)
{
if((cub[i].l!=cub[j].l)&&(cub[i].w>cub[j].w))
{
f[i]=max(f[i],f[j]+cub[i].h);
}
}
}
}
void print()
{
static int pos=0;
int ans=0;
for(
int i=0;i<cnt;i++)
ans=max(f[i],ans);
printf("Case %d: maximum height = %d\n",++pos,ans);
}
int main()
{
while(input())
{
sort(cub,cub+cnt,cmp);
//for(int i=0;i<cnt;i++)
// printf("%d %d %d\n",cub[i].l,cub[i].w,cub[i].h);
DP();
print();
}
return 0;
}