首页 > 代码库 > [HDU 1069]Monkey and Banana(DP)
[HDU 1069]Monkey and Banana(DP)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1069
题目大意:给你n个积木,告诉你它们的长宽高,要你搭出一个塔,这个塔上面的积木长和宽必须小于下面积木的长和宽,求这个塔的最大高度
思路:将n块积木转化成3*n块积木,相当于每块积木的原来状态、翻转后的状态。然后对这3n个积木按高度排序,此题就变成了一个类似于求最长下降子序列的问题
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #define MAXN 1000 using namespace std; struct Box { int x,y,z; //我们定义z为箱子高度 }boxes[MAXN]; int cnt=0; int f[MAXN]; //f[i]=前i个箱子得到的最大高度 bool cmp(Box a,Box b) { if(a.x!=b.x) return a.x>b.x; else return a.y>b.y; } int main() { int n,TestCase=0; while(scanf("%d",&n)!=EOF&&n) { cnt=0; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { int p[4]; for(int i=1;i<=3;i++) scanf("%d",&p[i]); sort(p+1,p+4); boxes[++cnt].x=p[3],boxes[cnt].y=p[2],boxes[cnt].z=p[1]; boxes[++cnt].x=p[3],boxes[cnt].y=p[1],boxes[cnt].z=p[2]; boxes[++cnt].x=p[2],boxes[cnt].y=p[1],boxes[cnt].z=p[3]; } sort(boxes+1,boxes+cnt+1,cmp); for(int i=1;i<=cnt;i++) f[i]=boxes[i].z; for(int i=cnt-1;i>=1;i--) for(int j=i+1;j<=cnt;j++) { if(boxes[i].x>boxes[j].x&&boxes[i].y>boxes[j].y) f[i]=max(f[i],f[j]+boxes[i].z); } int ans=f[1]; for(int i=1;i<=cnt;i++) if(f[i]>ans) ans=f[i]; printf("Case %d: maximum height = %d\n",++TestCase,ans); } return 0; }
[HDU 1069]Monkey and Banana(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。