首页 > 代码库 > uva--437The Tower of Babylon+dp
uva--437The Tower of Babylon+dp
题意:
给定一些立方体,对于两个立方体,只有其中一个底面两个边都严格小于另一个才可以放在其上面。求可以得到的最大高度。
思路:
一个立方体可以转成6个底面不同的具有不同权值(高度)的矩形,然后就是这些矩形的嵌套问题了。以前是将这个问题转成了DAG图上的最长路做的;这一次直接将这些矩形按照底面积由小到大的排序,然后问题就变成求最长上升子序列了。
代码如下:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int k; typedef struct { int x,y,z; }S; S st[200]; int cmp(S s1,S s2) { return s1.x*s1.y>s2.x*s2.y; } int main() { int n,Case=0; while(scanf("%d",&n)&&n) { k=1; for(int i=0;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); st[k].x=x; st[k].y=y; st[k].z=z; k++; st[k].x=y; st[k].y=x; st[k].z=z; k++; st[k].x=z; st[k].y=x; st[k].z=y; k++; st[k].x=x; st[k].y=z; st[k].z=y; k++; st[k].x=z; st[k].y=y; st[k].z=x; k++; st[k].x=y; st[k].y=z; st[k].z=x; k++; } sort(st+1,st+k,cmp); int dp[200],ans=0; for(int i=1;i<k;i++) dp[i]=st[i].z; for(int i=1;i<k;i++) for(int j=1;j<i;j++) { if(st[i].x<st[j].x&&st[i].y<st[j].y) { dp[i]=max(dp[i],dp[j]+st[i].z); ans=max(ans,dp[i]); } } printf("Case %d: maximum height = %d\n",++Case,ans); } return 0; }
uva--437The Tower of Babylon+dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。