Monkey and Banana （hdu 1069）

http://acm.hdu.edu.cn/showproblem.php?pid=1069

 

题目描述：

给你n个箱子， 给你箱子的长宽高，箱子是可以无限使用的，问这些箱子摞起来最多能多高？ 这些箱子摞起来有个规定，下面箱子的长和宽必须大于上面箱子的长和宽。

 

DP思路：dp[i]  代表第  i  个箱子在最上方的时候所摞起来的最大高度。

 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
 
#define EPS 1e-6
#define INF 0x3f3f3f3f
#define N 1000
#define met(a,b) (memset(a,b,sizeof(a)))
 
struct Box
{
    int L, W, H;
    Box(int LL=0, int WW=0, int HH=0):L(LL), W(WW), H(HH)
    {
        if(L>W) swap(L, W);
    }
    bool friend operator < (Box n1, Box n2)
    {
        if(n1.L != n2.L)
            return n1.L > n2.L;
        else if(n1.W != n2.W)
            return n1.W > n2.W;
        return n1.H > n2.H;
    }
}a[N];
 
int dp[N];
 
int main()
{
    int n, iCase=1;
 
    while(scanf("%d", &n), n)
    {
        int i, j, x, y, z, k=0, Max = 0;
 
        met(a, 0);
        met(dp, 0);
 
        for(i=0; i<n; i++)
        {
            scanf("%d%d%d", &x, &y, &z);
            a[k++] = Box(x, y, z);
            a[k++] = Box(x, z, y);
            a[k++] = Box(y, z, x);
        }
 
        sort(a, a+k);
 
        for(i=0; i<k; i++)
        {
            dp[i] = a[i].H;
            for(j=0; j<i; j++)
            {
                if(a[i].L<a[j].L && a[i].W<a[j].W)
                    dp[i] = max(dp[i], dp[j] + a[i].H);
            }
            Max = max(Max, dp[i]);
        }
 
        printf("Case %d: maximum height = %d
", iCase++, Max);
    }
    return 0;
}