POJ 2392 Space Elevator

題意：
    K種不同的磚塊，每種磚塊的高度為h，能蓋的最大高度為a，數量為c，由於安全考量，所以當現在蓋的高度超過該種磚塊的a時，就不能再用該種磚塊，求最大能蓋的高度？
    例如sample input，第二種磚塊的高度為23，所以如果現在建築物蓋到24以上，就只能用第一種和第三種磚塊繼續蓋。

想法：
    這題要先將磚塊的a値由小到大排序，再做背包問題，算是一種greedy的方式，把a値小的磚塊盡可能放在底層，否則無法達到最大高度。
    例如底下左邊這組，答案是4，如果不排序成右邊的話，算出的結果會<4。
2         2
1 4 3     2 2 1
2 2 1     1 4 3
    且最後要枚舉一下dp的每個値找出最大値，因為最大値不一定位在dp的最後一個位置。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int dp[40005] = {0};
	struct Block{
	int h;
	int a;
	int c;
	}b[401];
	bool cmp(const Block &a, const Block &b)
	{
	return a.a < b.a;
	}
	int main()
	{
	int K;
	while (scanf("%d", &K) != EOF) {
	// Input
	for (int k = 0; k < K; ++k)
	scanf("%d %d %d", &b[k].h, &b[k].a, &b[k].c);
	sort(b, b+K, cmp);
	// Knapsack
	fill(dp, dp+40005, 0);
	for (int k = 0; k < K; ++k)
	for (int i = 0; i < b[k].c; ++i)
	for (int j = b[k].a; j-b[k].h >= 0; --j)
	dp[j] = max(dp[j], dp[j-b[k].h] + b[k].h);
	// Ouput
	int ans = 0;
	for (int i = 0; i <= b[K-1].a; ++i)
	ans = max(ans, dp[i]);
	printf("%d\n", ans);
	}
	}

view raw [POJ] 2392 Space Elevator.cpp hosted with ❤ by GitHub