POJ 2392 Space Elevator 题解 《挑战程序设计竞赛(第2版)》

POJ 2392 Space Elevator

通天塔：奶牛们想用c_i个高h_i的积木造通天塔，每种积木不能高过a_i，求塔的最大高度。

多重背包 O(VN) 单调队列 

这题要思考的方向是往多重背包这边想，高度既是“价值”又是“重量”，背包的容积是变动的a_i。性价比恒为1，优先使用a_i小的。必须按积木的a_i从小到大的顺序递推才能覆盖全部解空间，否则a_i小的积木根本码不上去。

多重背包的O(VN)优化是利用单调队列实现，我从这里现学现卖。

《2.3 记录结果再利用的“动态规划” 需稍加思考的题目》

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

int f[2][40000 + 16];
pair <int, int> q[40000 + 16];			// 单调队列 first := 最优解 second:= 容积

struct Block
{
	int h, a, c;
	bool operator < (const Block & b) const
	{
		return a < b.a;
	}
};

Block block[400 + 16];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int K;
	cin >> K;
	for (int i = 0; i < K; ++i)
	{
		cin >> block[i].h >> block[i].a >> block[i].c;
	}
	sort(block, block + K);

	int cur = 0, pre = 1;
	for (int i = 0; i < K; ++i)
	{
		swap(cur, pre);
		int v, w, m;
		v = block[i].h;
		w = block[i].h;
		m = block[i].c;
		int V = block[i].a;
					// 价值 重量 数量
		for (int mod = 0; mod < w; ++mod)
		{
			int l = 0, r = 0;		// 单调队列 首 尾
			for (int j = 0; mod + j * w <= V; ++j)
			{
				// 维持单调队列的递减特性
				while (r > l && (f[pre][mod + j * w] - j * v) > q[r - 1].first)
				{
					// 将前面小的元素都挤出去
					r--;
				}
				// 入队
				q[r++] = make_pair(f[pre][mod + j * w] - j * v, j);
				if (r - l > 0 && j - q[l].second > m)
				{
					// 队列不为空，最优解对应的缺口无法填满，出队
					l++;
				}
				f[cur][mod + j * w] = q[l].first + j * v;
			}
		}
	}

	cout << *max_element(f[cur], f[cur] + block[K - 1].a + 1) << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

马上要开始工作了，接着就开学，可能会减慢看《挑战程序设计竞赛(第2版)》的速度了。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2392 Space Elevator 题解 《挑战程序设计竞赛(第2版)》