首页 > 代码库 > UVa 437 (变形的LIS) The Tower of Babylon
UVa 437 (变形的LIS) The Tower of Babylon
题意：
有n种类型的长方体，每种长方体的个数都有无限个。当一个长方体的长和宽分别严格小于另一个长方体的长和宽的时候，才可以把这个放到第二个上面去。输出这n种长方体能组成的最大长度。
分析：
虽说每种都有无限个，可每种长方体一共的“姿态”最多也只有三种，将它们三个边长分别作为高。然后按照底面排序，就转化为最大上升子列的问题。
代码中采用了“人人为我”的方法。
1 //#define LOCAL 2 #include <iostream> 3 #include <algorithm> 4 #include <cstdio> 5 #include <cstring> 6 using namespace std; 7 8 const int maxn = 100; 9 struct Cube10 {11 int x, y, z;12 bool operator< (const Cube& a) const13 { return x < a.x || (x == a.x && y < a.y); }14 }cubes[maxn];15 int size[3], dp[maxn];16 17 bool check(int a, int b)18 {19 return (cubes[a].x < cubes[b].x && cubes[a].y < cubes[b].y);20 }21 22 int main(void)23 {24 #ifdef LOCAL25 freopen("437in.txt", "r", stdin);26 #endif27 28 int n, kase = 0;29 while(scanf("%d",&n) == 1 && n)30 {31 for(int i = 0; i < n; ++i)32 {33 for(int j = 0; j < 3; ++j) scanf("%d", &size[j]);34 sort(size, size + 3);35 cubes[i*3].x = size[0], cubes[i*3].y = size[1], cubes[i*3].z = size[2];36 cubes[i*3+1].x = size[0], cubes[i*3+1].y = size[2], cubes[i*3+1].z = size[1];37 cubes[i*3+2].x = size[1], cubes[i*3+2].y = size[2], cubes[i*3+2].z = size[0];38 }39 n *= 3;40 sort(cubes, cubes + n);41 memset(dp, 0, sizeof(dp));42 for(int i = 0; i < n; ++i) dp[i] = cubes[i].z;43 for(int i = 1; i < n; ++i)44 for(int j = 0; j < i; ++j)45 if(check(j, i)) dp[i] = max(dp[i], cubes[i].z + dp[j]);46 int ans = 0;47 for(int i = 0; i < n; ++i) ans = max(ans, dp[i]);48 printf("Case %d: maximum height = %d\n", ++kase, ans);49 }50 51 return 0;52 }
UVa 437 (变形的LIS) The Tower of Babylon
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。