// 343. 太空电梯 Space Elevator（挑战程序设计竞赛）.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include #include #include using namespace std; /* https://www.papamelon.com/problem/343 奶牛们要去太空了！它们打算用方块建造一座太空电梯。现在它们有 N 种方块，第 i 种方块有一个特定的高度 h_i，一定的数量 c_i。为了防止宇宙射线的破坏方块，第 i 种方块的任何部分不能超过高度 a_i。请用这些方块堆出最高的太空电梯。输入第一行，一个整数 N 第二行到 N+1 行，每行三个整数 h_i,a_i,c_i，数字之间用空格分隔。 1≤hi≤100，1≤ci≤10，1≤ai≤4×10^4 输出一个整数，为太空电梯的高度。样例 1 输入 3 7 40 3 5 23 8 2 52 6 输出 48 */ const int N = 410; const int M = 40010; int dp[2][M]; int n; struct BLOCK { int a, c, h; }blocks[M]; bool cmp(const struct BLOCK& a, const struct BLOCK& b) { return a.a < b.a; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> blocks[i].h >> blocks[i].a >> blocks[i].c; } sort(blocks + 1, blocks + 1 + n, cmp); memset(dp, -1, sizeof dp); dp[0][0] = 0; int* prev = dp[0]; int* curr = dp[1]; for (int i = 1; i <= n; i++) { int debug = 1; for (int j = 0; j < M; j++) { if (prev[j] >= 0) curr[j] = 0; if (-1 == curr[j] && j <= blocks[i].a && j >= blocks[i].h && curr[j - blocks[i].h] >= 0 && curr[j - blocks[i].h] + 1 <= blocks[i].c) { curr[j] = curr[j - blocks[i].h] + 1; } //cout << "j = " << j << endl; } swap(prev, curr); } for (int i = M-1; i >= 0; i--) { if (prev[i] != -1) { cout << i << endl; break; } } return 0; }