首页 > 代码库 > hdu 1069 Monkey and Banana (dp)
hdu 1069 Monkey and Banana (dp)
//把给定的长方体(不限)叠加在一起,叠加的条件是,上面一个长方体的长和宽都比下面长方体的长 /* 分析:因为每块积木最多有3个不同的底面和高度,因此先把每块积木看成三种不同的积木, 每种积木只有一个底面和一个高度。n中类型的积木转化为3*n个不同的积木的叠加, 对这3 * n个积木的长边从大到小排序;接下来的问题就是找到一个递减的子序列, 使得子序列的高度和最大即可。 数组dp:dp[i]表示是以第i块积木为顶的塔的最大高度 因此可得状态转移方程:dp[i] = max(dp[i],dp[j] + r[i].z)(满足积木j的底面长和宽都大于积木i的长和宽) 和宽短;求这些长方体能叠加的最高的高度. */ # include <stdio.h> # include <string.h> # include <algorithm> using namespace std; struct node { int x; int y; int z; }; struct node r[100010]; bool cmp(node a1,node a2) { if(a1.x!=a2.x) return a1.x>a2.x; return a1.y>a2.y; } int main() { int cas=0; int i,j,n,a,b,c,maxh; int dp[100010]; while(~scanf("%d",&n),n) { for(i=0,j=0; i<n; i++) { scanf("%d%d%d",&a,&b,&c); r[j].x=min(a,b); r[j].y=max(a,b); r[j].z=c; r[j+1].x=min(a,c); r[j+1].y=max(a,c); r[j+1].z=b; r[j+2].x=min(b,c); r[j+2].y=max(b,c); r[j+2].z=a; j+=3; } n=j; sort(r,r+n,cmp); for(i=0; i<n; i++) dp[i]=r[i].z; maxh=0; for(i=0; i<n; i++) { for(j=i-1; j>=0; j--) { if(r[j].x>r[i].x&&r[j].y>r[i].y) { if(dp[j]+r[i].z>dp[i]) dp[i]=dp[j]+r[i].z; } } if(maxh<dp[i]) maxh=dp[i]; } printf("Case %d: maximum height = %d\n",++cas,maxh); } return 0; }
hdu 1069 Monkey and Banana (dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。