首页 > 代码库 > UVA 437 The Tower of Babylon
UVA 437 The Tower of Babylon
题意:给n种立体块,每种有无限个,上面的块长宽必须小于下面的块,问最多可以搭建多高
思路:输入的时候小小处理下,把每个块各条边当高的情况存入结构体中,按升序排序,然后dp,比较求出最大值。。看好多代码都说什么最长上升子序列,感觉没有用到额,LIS的标记数组是用来存储相应长度的最小值的,没看出来哪里用上了额。。。数据范围小,直接就是dp了=。=
#include <iostream> #include <stdio.h> #include <string> #include <cstring> #include <algorithm> #include <cmath> #define N 200 using namespace std; struct Node { int x,y,z; void fun(int a,int b,int c) { x=a;y=b;z=c; } }f[N]; int dp[N]; int cmp(Node a,Node b) { if(a.x*a.y<b.x*b.y) return 1; return 0; } int main() { int n; int x,y,z; int ca=1; while(~scanf("%d",&n)) { if(n==0) break; int m=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); f[m++].fun(x,y,z); f[m++].fun(x,z,y); f[m++].fun(y,x,z); f[m++].fun(y,z,x); f[m++].fun(z,x,y); f[m++].fun(z,y,x); } sort(f,f+m,cmp); int ans=0; for(int i=1;i<=m;i++) { dp[i]=f[i].z; for(int j=1;j<i;j++) { if(f[j].x<f[i].x&&f[j].y<f[i].y) dp[i]=max(dp[i],dp[j]+f[i].z); } if(dp[i]>ans) ans=dp[i]; } printf("Case %d: maximum height = %d\n",ca++,ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。