HDU 1069 Monkey and Banana（DP）

大意：把给定的长方体（不限个数）叠加在一起，上面的长和宽比下面的长和宽短，求这些长方体加起来的最高高度。

思路：每个格子最多3个状态，也就是高最多有3种，也就是一共有N*3 最多90个格子，但是X和Y可以对调，那么就最多180个，对180个格子对X从小到大排序，X相等，Y就从小到大排序，那么这个问题就可以转换成类似求最大递增子序列问题一样思路的DP，DP[i]表示第i个格子时的最大值，dp[i+1]就是从前i个中找符合条件的最大的一个加上去。

 1 #include <map>
 2 #include <stack>
 3 #include <queue>
 4 #include <math.h>
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <iostream>
 8 #include <algorithm>
 9 #define LL __int64
10 using namespace std;
11 #define N 100
12 
13 struct node
14 {
15     int x, y, z;
16 } dp[N*N];
17 
18 int cmp(const void *a, const void *b)
19 {
20     node *c = (node *)a;
21     node *d = (node *)b;
22     if(c -> x != d -> x)
23         return c -> x - d -> x;
24     return c -> y - d -> y;
25 }
26 
27 void run()
28 {
29     int n;
30     int x, y, z;
31     int cnt = 1;
32     while(~scanf("%d", &n) && n)
33     {
34         int t = 0;
35         for(int i = 1; i <= n; i++)
36         {
37             scanf("%d%d%d", &x, &y, &z);
38             ///列出这种x，y，z，对应的所有3*6=18种情况
39             dp[t].x = x, dp[t].y = y, dp[t++].z = z;        
40             dp[t].x = x, dp[t].y = z, dp[t++].z = y;
41             dp[t].x = y, dp[t].y = x, dp[t++].z = z;
42             dp[t].x = y, dp[t].y = z, dp[t++].z = x;
43             dp[t].x = z, dp[t].y = x, dp[t++].z = y;
44             dp[t].x = z, dp[t].y = y, dp[t++].z = x;
45         }
46         ///对所有情况排序，先按x排序，x相等就按y排序
47         qsort(dp, t, sizeof(dp[0]), cmp);
48         for(int i = 1; i < t; i++)
49         {
50             ///DP[i]表示第i个格子时的最大值，
51             ///DP[i+1]就是从前i个中找符合条件的最大的一个加上去。
52             int ans = 0;
53             for(int j = 0; j < i; j++)
54             {
55                 if((dp[j].x < dp[i].x && dp[j].y < dp[i].y) && dp[j].z > ans)
56                     ans = dp[j].z;
57             }
58             dp[i].z += ans;
59         }
60         int Max = 0;
61         for(int i = 0; i < t; i++)
62         {
63             if(dp[i].z > Max)
64                 Max = dp[i].z;
65         }
66         printf("Case %d: maximum height = %d
", cnt++, Max);
67     }
68 }
69 
70 int main(void)
71 {
72     run();
73 
74     return 0;
75 }

Monkey and Banana

HDU 1069 Monkey and Banana（DP）

相关推荐