hdu 1069 Monkey and Banana

题意：有n个长方体盒子，要把他垒成梯子，垒起来的时候可以翻转。

已知每个盒子的长宽高，盒子a能垒在盒子b上的要求是盒子a底面的两条边小于

盒子b底面的两条边。问最多能垒多高。

分析：

由于可以翻转，则对应了3*n种盒子。按照得到的3*n中盒子的长宽排序。

先按长递减排序，长相等的按宽递减排序。

枚举每个盒子，分别向前递推能够放在当前盒子下的最大高度。然后更新

当前盒子为顶垒成的最大高度，用dp[i]记录下来。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

struct node
{
    int h,l,w;
}rec[100];
int dp[100];

int maxx(int x,int y)
{
    return x>y?x:y;
}

bool cmp(node x,node y)
{
    if(x.l == y.l)
        return x.w>y.w;
    return x.l>y.l;
}

int main()
{
    int n,a,b,c,t,ans,cnt,tmp,cas=1;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            rec[cnt].l=a>b?a:b;
            rec[cnt].w=a<b?a:b;
            rec[cnt++].h=c;
            rec[cnt].l=a>c?a:c;
            rec[cnt].w=a<c?a:c;
            rec[cnt++].h=b;
            rec[cnt].l=b>c?b:c;
            rec[cnt].w=b<c?b:c;
            rec[cnt++].h=a;
        }
        sort(rec,rec+cnt,cmp);
        memset(dp,0,sizeof(dp));
        dp[0]=rec[0].h;
        for(int i=1;i<cnt;i++)
        {
            tmp=0;
            for(int j=i-1;j>=0;j--)
            {
                if((rec[i].l<rec[j].l && rec[i].w<rec[j].w)||
               (rec[i].l<rec[j].w && rec[i].w<rec[j].l))
                {
                    if(dp[j]>tmp)
                        tmp=dp[j];
                }
            }
            dp[i]=tmp+rec[i].h;
        }
        ans=-1;
        for(int i=0;i<cnt;i++)
        {
            if(dp[i]>ans)
                ans=dp[i];
        }
        printf("Case %d: maximum height = %d\n",cas++,ans);
    }
    return 0;
}

hdu 1069 Monkey and Banana

原文：http://blog.csdn.net/u012841845/article/details/18799771