大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
题意:给你一个数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; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118679.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...