首页 > 代码库 > HDU 1069 Monkey and Banana
HDU 1069 Monkey and Banana
题意:给你一个数n,接下来给你一个矩形体的3边长(即随便你怎么放它,它的高度有可能是3边中的一条边),现在要你求出这n个矩形体能堆成一座塔的最高高度(塔就是面积从店面开始向上严格递增)
思路:动规里的最长子序列的变形,结合了贪心的思想。首先我们需要对你所用的高进行排序,排序之后找出最严格递减的面积就可以了
AC代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct node { int l,w,h; }box[111]; int dp[111]; bool cmp(node a,node b) { if(a.l>b.l) return true; if(a.l==b.l&&a.w>b.w) return true; return false; } int main() { int d[3],n,i,j,c=1,k,sumh; while(scanf("%d",&n)!=EOF&&n) { k=0; for(i=0;i<n;i++) { scanf("%d%d%d",&d[0],&d[1],&d[2]); sort(d,d+3); box[k].l=d[2];box[k].w=d[1];box[k].h=d[0];k++; //每个矩形体有3中放的方式 box[k].l=d[2];box[k].w=d[0];box[k].h=d[1];k++; box[k].l=d[1];box[k].w=d[0];box[k].h=d[2];k++; } sort(box,box+k,cmp); /* for(i=0;i<k;i++) printf("%d %d %d\n",box[i].l,box[i].w,box[i].h);*/ for(i=0;i<k;i++) dp[i]=box[i].h; for(i=k-2;i>=0;i--) for(j=i+1;j<k;j++) { if(box[i].l>box[j].l&&box[i].w>box[j].w) //寻求严格递减的面积 if(dp[i]<dp[j]+box[i].h) dp[i]=dp[j]+box[i].h; } sumh=dp[0]; for(i=0;i<k;i++) if(sumh<dp[i]) sumh=dp[i]; printf("Case %d: maximum height = %d\n",c++,sumh); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。