HDU1069MonkeyandBanana

HDU 动态规划 贪心

题意

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

想法

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

1. 要么保证长比宽长&＃xff0c;每次录入3个面
2. 要么每次录入6个面
   因为这个卡了好久

代码

15ms

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