POJ 2392 Space Elevator

Space Elevator

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 5 Accepted Submission(s) : 3

Problem Description

The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 <= K <= 400) different types of blocks with which to build the tower. Each block of type i has height h_i (1 <= h_i <= 100) and is available in quantity c_i (1 <= c_i <= 10). Due to possible damage caused by cosmic rays, no part of a block of type i can exceed a maximum altitude a_i (1 <= a_i <= 40000).

Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.

Input

* Line 1: A single integer, K <br> <br>* Lines 2..K+1: Each line contains three space-separated integers: h_i, a_i, and c_i. Line i+1 describes block type i.

Output

* Line 1: A single integer H, the maximum height of a tower that can be built

Sample Input

3 7 40 3 5 23 8 2 52 6

Sample Output

题意:有一群牛要上太空,他们计划建一个太空梯(用一些石头垒),他们有k种不同类型的石头,每一种石头的高度为h,数量为c,由于会受到太空辐射,每一种石头不能超过这种石头的最大建造高度a,求解利用这些石头所能修建的太空梯的最高的高度.
多重背包问题,与一般的多重背包问题所不同的知识多了一个限制条件就是某些"物品"叠加起来的"高度"不能超过一个值,于是我们可以对他们的最高可能达到高度进行排序,然后就是一般的多重背包问题了

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <cstdio>
 5 #include <algorithm>
 6 using namespace std;
 7 int dp[400005];
 8 int v[40005];
 9 struct node
10 {
11     int h,a,c;
12 }g[40005];
13 bool cmp(node a, node b)
14 {
15     return a.a < b.a;
16 }
17 int main()
18 {
19     int k;
20     cin >> k;
21     int j, i;
22     for (i = 1; i <= k; i++)
23     {
24         cin >> g[i].h >> g[i].a >> g[i].c;
25     }
26     memset(dp, 0, sizeof(dp));
27     dp[0] = 1;
28     sort(g + 1, g + k + 1, cmp);
29     int ans = 0;
30     for (i = 1; i <= k; i++)
31     {
32         memset(v, 0, sizeof(v));//记录当前用了几个g[i]
33         for (j = g[i].h; j <= g[i].a; j++)
34         {
35             if (!dp[j] && dp[j - g[i].h] && v[j - g[i].h] + 1 <= g[i].c)
36             {//dp用来记录能不能达到着高度
37                 dp[j] = 1;
38                 v[j] = v[j - g[i].h] + 1;
39                 if (ans < j)
40                     ans = j;
41             }
42         }
43     }
44     cout << ans << endl;
45     return 0;
46 }