首页 > 代码库 > HDU 1069 Monkey and Banana

HDU 1069 Monkey and Banana

2024-07-13 17:30:52   220人阅读

单调递增子序列的变形，一种长方体虽说可以有无限个，但它最多有3中摆放方法(我们假设x方向的长度不小于y方向的长度)。

然后对x递减一级排序，y递减二级排序，相当于按面积递减排序。

dp初始化就是对应状态的长方体的高度

如果第j个长方体的x，y分别（严格）大于第i个长方体的x，y　　　　（这里排序后的j<i）

说明第j个长方体可以放在第i个长方体的下面

更新垒起来的长度

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 struct Cube 9 {10     int x, y, z;11 }cube[100];12 13 int dp[100];14 15 bool cmp(Cube a, Cube b)16 {17     if(a.x != b.x)18         return (a.x > b.x);19     return (a.y > b.y);20 }21 22 int main(void)23 {24     #ifdef LOCAL25         freopen("1069in.txt", "r", stdin);26     #endif27 28     int n, kase = 0;29     while(scanf("%d", &n) && n)30     {31         int i, j;32         for(i = 0; i < n; ++i)33         {34             int x, y, z;35             scanf("%d%d%d", &x, &y, &z);36             cube[i*3].z = z;37             cube[i*3].x = max(x, y);38             cube[i*3].y = min(x, y);39 40             cube[i*3 + 1].z = x;41             cube[i*3 + 1].x = max(y, z);42             cube[i*3 + 1].y = min(y, z);43 44             cube[i*3 + 2].z = y;45             cube[i*3 + 2].x = max(x, z);46             cube[i*3 + 2].y = min(x, z);47         }48         sort(cube, cube + n*3, cmp);49 50         for(i = 0; i < n*3; ++i)51             dp[i] = cube[i].z;52         for(i = 1; i < n*3; ++i)53             for(j = 0; j < i; ++j)54             {55 56                 if(cube[j].x > cube[i].x 57                     && cube[j].y > cube[i].y)58                     dp[i] = max(dp[i], dp[j] + cube[i].z);59             }60 61         int ans = cube[0].z;62         for(i = 0; i < n*3; ++i)63             ans = max(ans, dp[i]);64         printf("Case %d: maximum height = %d\n", ++kase, ans);65     }66     return 0;67 }
代码君


联系
我们