Space Elevator
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
* 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
Hint
OUTPUT DETAILS:
From the bottom: 3 blocks of type 2, below 3 of type 1, below 6 of type 3. Stacking 4 blocks of type 2 and 3 of type 1 is not legal, since the top of the last type 1 block would exceed height 40.
Source
题目类型：多重背包
算法分析：这里先使用一个贪心思想是先按照限制高度从小到大排序，然后再直接计算一个多重背包即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
/************************************************** filename :g.cpp author :maksyuki created time :2017/2/12 9:57:26 last modified :2017/2/12 10:19:43 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CPPFF ifstream cin ("in") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 4e5 + 6666; struct point { int h, a, c; bool operator < (const point &b) const { return a < b.a; } }; point p[400+66]; int dp[maxn]; int main() { //CFF; //CPPFF; int K; while(scanf("%d", &K) != EOF) { int W = -INF; for(int i = 1; i <= K; i++) { scanf("%d%d%d", &p[i].h, &p[i].a, &p[i].c); W = max(W, p[i].a); } sort(p + 1, p + 1 + K); memset(dp, 0, sizeof(dp)); for(int i = 1; i <= K; i++) { if(p[i].c * p[i].h >= p[i].a) { for(int j = p[i].h; j <= p[i].a; j++) dp[j] = max(dp[j], dp[j-p[i].h] + p[i].h); } else { int k = 1; while(k < p[i].c) { for(int j = p[i].a; j >= k * p[i].h; j--) dp[j] = max(dp[j], dp[j-k*p[i].h] + k * p[i].h); p[i].c -= k; k <<= 1; } for(int j = p[i].a; j >= p[i].c * p[i].h; j--) dp[j] = max(dp[j], dp[j-p[i].c*p[i].h] + p[i].c * p[i].h); } } int res = -INF; for(int i = 0; i <= W; i++) res = max(res, dp[i]); printf("%d\n", res); } return 0; } |
- « 上一篇：poj3666
- poj1844：下一篇 »