poj2392(Space Elevator)
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.
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.
* 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.
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.
题意：给你一些石头，告诉你每种石头的高度、能堆的最大高度、数量，求所有石头能堆最大高度是多少。
题解：先按能堆的最大高度对石头从小到大进行排序，然后就是一个多重背包问题。
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;
struct block
{
int h, a, c;
bool operator < (const block& b) const
{
return a < b.a;
}
};
int k, sum[40010], dp[40010];
block s[410];
int main()
{
cin >> k;
for (int i = 0; i < k; ++i)
scanf("%d%d%d", &s[i].h, &s[i].a, &s[i].c);
sort(s, s+k);
dp[0] = 1;
int ans = 0;
for (int i = 0; i < k; ++i)
{
memset(sum, 0, sizeof(sum));
for (int j = s[i].h; j <= s[i].a; ++j)
if (dp[j-s[i].h] && !dp[j] && sum[j-s[i].h] < s[i].c)
{
dp[j] = 1;
sum[j] = sum[j-s[i].h] + 1;
ans = max(ans, j);
}
}
cout << ans << endl;
return 0;
}算法码上来 文章被收录于专栏
公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。
