HDU 1069 Monkey and Banana-蒲公英云

HDU 1069 Monkey and Banana

原题目链接：HDU1069

分类

HDU 动态规划贪心

题意

题意是堆箱子、要求上面的箱子的长和宽都小于下面箱子的长和宽

想法

因为每块砖有三种摆法（高和底面积不同），可以把这三种情况当成不同的三块砖，加入brick数组中。注意，一定要分清长和宽，长要比宽长，这样在后面dp的过程中可以保证长边和长边比较、短边和短边比较。
所以

要么保证长比宽长，每次录入3个面
要么每次录入6个面
因为这个卡了好久

代码

15ms

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/17 */
#include <bits/stdc++.h>
using namespace std;
int dp[2000];
struct node{ 
    int l, w, h;
}brick[2000]; 
bool cmp(node a, node b)
{ 
    if(a.l != b.l){ 
        return a.l > b.l; 
    }else{ 
        return a.w > b.w;
    }
}
int main()
{ 
    int n;
    int tmp[3], ans, k;
    int kase  = 0;
    while(scanf("%d",&n)!=EOF){ 
        if(n ==0){ 
            return 0;
        }
        k = 0;
        for(int i =0;i < n;i++){ 
            scanf("%d%d%d",&tmp[0],&tmp[1],&tmp[2]);
            sort(tmp,tmp+3);
            brick[k].l=tmp[0];
            brick[k].w=tmp[1];
            brick[k++].h=tmp[2];
            brick[k].l=tmp[1];
            brick[k].w=tmp[2];
            brick[k++].h=tmp[0];
            brick[k].l=tmp[0];
            brick[k].w=tmp[2];
            brick[k++].h=tmp[1];
        }
        sort(brick, brick + k, cmp);
        ans = -1;
        for(int i = 0;i < k;i++){ //遍历所有砖块
            dp[i] = brick[i].h;//dp[i]代表以第i块砖为顶的塔的最大高度
            //初始值是i砖块的高度（最坏的情况就是塔只有i一块砖）
            for(int j= i-1;j >=0; j--){ //开始决定i砖块底下的砖是什么
                if(brick[j].l > brick[i].l && brick[j].w > brick[i].w){ //如果j砖块符合条件
                    dp[i] = max(dp[i], dp[j] + brick[i].h);
                    //放在以j砖块为顶的塔上是否比原来的值大
                }
            }
            ans = max(ans, dp[i]);//答案是所有dp中的最大值
        }
        printf("Case %d: maximum height = %d\n",++kase,ans);
    }
}