好贷网好贷款

Hdu 1069 Monkey and Banana -- DP

发布时间:2016-12-5 2:23:47 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Hdu 1069 Monkey and Banana -- DP",主要涉及到Hdu 1069 Monkey and Banana -- DP方面的内容,对于Hdu 1069 Monkey and Banana -- DP感兴趣的同学可以参考一下。

/* 题意:给你n个箱子,有长宽高,箱子的个数不限,让你把它们摞起来以得到最高的高度。摞起来的规则是:上面箱子的长宽必须严格小于下面箱子的对应长宽。 箱子可以翻转。 分析:按 立起来是长、宽、高将一个箱子看做是三个箱子。对长宽进行排序,再从最大的搜到最小的,每次更新得到的最大高度,即可得到结果。 也可以用弗洛伊德求最长路的思想来做。 */ #include<stdio.h> #include<algorithm> using namespace std; struct block{ int x,y,z; }a[100]; bool cmp(block a,block b) { if(a.x=b.x)return a.y>b.y; return a.x>b.x; } int num; void div(int x,int y ,int z) { a[num].x = x>y?x:y; a[num].y = x+y-a[num].x; a[num].z = z; num++; } int main() { int n;int x,y,z,ans,c; c = 0; while (scanf("%d",&n)!=EOF) { if(n==0)break; int h[105] = {0}; num = 0;ans = 0; for (int i = 0; i < n; i++) { scanf("%d %d %d",&x,&y,&z); div(x,y,z); div(x,z,y); div(y,z,x); } sort(a,a+num,cmp); for (int i = 0; i < num; i++)//h[i]表示以a[i].x,a[i].y为底所能得到的最大高度。 { h[i] = 0; for (int j = i-1; j >= 0; j--)//每次都往前面去查。 { if(a[i].x<a[j].x && a[i].y<a[j].y && h[j]>h[i]) h[i] = h[j]; } h[i] += a[i].z; if(h[i] > ans) ans = h[i]; } printf("Case %d: maximum height = %d\n",++c,ans); } return 0; }

上一篇:TIFF文件读取
下一篇:Surround the Trees

相关文章

相关评论