HDU 1069 Monkey and Banana

一时失言乱红尘 2022-04-16 05:53 176阅读 0赞

## 原题目链接：[HDU1069][] ##

--------------------

## 分类 ##

HDU 动态规划 贪心

--------------------

## 题意 ##

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

--------------------

## 想法 ##

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

1.  要么保证长比宽长，每次录入3个面
2.  要么每次录入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);
    	}
    }

--------------------

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