【题解】「P6771」[USACO05MAR]Space Elevator 太空电梯

P6771

这是一道很明显的 dp 问题。

首先 dp 最重要的三要素是：动态表示、动态转移、初始状态。
只要这三个要素搞明白了，基本就能把这题做出来了。

solution

让我们来看看这题的动态表示、动态转移和初始状态。

状态表示：
(dp_{i,j}) 表示用前 (i) 种方块是否可以拼成高度 (j)

状态转移：
( dp_{i,j}= egin{cases}\\\\\end{cases} egin{matrix} dp_{i-1,j} && ext{用}0 ext{块第}i ext{种方块}\ dp_{i-1,j-h_{i}} && ext{用}1 ext{块第}i ext{种方块}\ &ldots&\ dp_{i-1,j-k imes h_{i}} && ext{用}k ext{块第i种方块}\ &ldots&\ dp_{i-1,j-c_{i} imes h_{i}} && ext{用}c_{i} ext{块第}i ext{种方块}\ end{matrix})
( dp_{i,j}|=dp{i,j-k imes h_{i}};(h_{i}le jle a_{i}, 1le kle c_i) )

初始状态：
(dp_{i,j}=mathrm{false};dp_{0,0}=mathrm{true})

最后物品维可以直接省掉，即：
(dp_{j}|=dp_{j-k imes h_{i}};(h_{i}le jle a_{i}, 1le kle c_i))

那么写出这三要素就很容易写出代码了

code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#define line cout << endl
using namespace std;

const int NR = 405;
struct node {
	int h, a, c;
};
node e[NR];
int n;
bool dp[40005];

bool cmp (node x, node y) {
	return x.a < y.a; 
}

int main () {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> e[i].h >> e[i].a >> e[i].c;
	dp[0] = true;
	sort (e + 1, e + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= e[i].c; j++) {
			for (int k = e[i].a; k >= e[i].h; k--) {
				dp[k] |= dp[k - e[i].h];//动态转移方程
			}
		}
	}
	for (int i = e[n].a; i >= 0; i--) {
		if (dp[i]) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}