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
48
题意:有一群牛要上太空,他们计划建一个太空梯(用一些石头垒),他们有k种不同类型的石头,每一种石头的高度为h,数量为c,由于会受到太空辐射,每一种石头不能超过这种石头的最大建造高度a,求解利用这些石头所能修建的太空梯的最高的高度. 多重背包问题,与一般的多重背包问题所不同的知识多了一个限制条件就是某些"物品"叠加起来的"高度"不能超过一个值,于是我们可以对他们的最高可能达到高度进行排序,然后就是一般的多重背包问题了
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 int dp[400005]; 8 int v[40005]; 9 struct node10 {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 }