Posted on 2012-03-23 10:37
C小加 閱讀(425)
評論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告
題意：把給定尺寸的長方體（數(shù)量不限）疊加在一起，疊加的條件是，上面一個(gè)長方體的長和寬比下面長方體的長和寬短，不能相等，長方體可以任意面朝下擺放，求這些長方體能疊加的最高的高度。
把每個(gè)長方體分成3個(gè)元素。然后就和矩形嵌套差不多了，排序之后求容量最大的子序列。
#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;
}