HDU 1069 Monkey and Banana

Description

n种盒子（不限量），摞起来最高能有多高？（上面盒子的长与宽必须都小于下面盒子的长与宽）

题目链接

思路

一种盒子六种摆放方式，将问题直接转化为：n * 6种（被规定以何种方式摆放的）盒子摞起来最高能有多高

dp：等同于求最长递减子序列

Code

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

const int N = 200;

struct node
{
    int L, W, H;
} box[N];

bool cmp(node a, node b)
{
    if(a.L != b.L)
        return a.L > b.L;
    else
    {
        if(a.W != b.W)
            return a.W > b.W;
        else
            return a.H > b.H;
    }
}

int main()
{
    int n, num = 1;
    while(~scanf("%d", &n) && n)
    {
        int a, b, c, cnt = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            box[cnt].L = a, box[cnt].W = b, box[cnt++].H = c;
            box[cnt].L = a, box[cnt].W = c, box[cnt++].H = b;
            box[cnt].L = b, box[cnt].W = a, box[cnt++].H = c;
            box[cnt].L = b, box[cnt].W = c, box[cnt++].H = a;
            box[cnt].L = c, box[cnt].W = a, box[cnt++].H = b;
            box[cnt].L = c, box[cnt].W = b, box[cnt++].H = a;
        }
        sort(box, box + cnt, cmp);
        int dp[N * 6];///dp[i]表示处理完i-1个箱子时的最大高度
        int ans = 0;
        for(int i = 0; i < cnt; ++i)
        {
            dp[i] = box[i].H;
            ///研究(条件满足时)dp[j]加上box[i].H能否更新dp[i]
            for(int j = 0; j < i; ++j)
                if(box[i].L < box[j].L && box[i].W < box[j].W)
                    dp[i] = max(dp[i], dp[j] + box[i].H);
            ans = max(ans, dp[i]);
        }
        printf("Case %d: maximum height = %d\n", num++, ans);
    }
    return 0;
}