自动搬运

查看原文

来自洛谷，原作者为

	Begemot **

搬运于2025-08-24 22:15:40，当前版本为作者最后更新于2024-08-29 21:43:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$f_{i,j}$ 表示大小为 $i\times j$ 的矩形的最小废料总面积。将 $f_{i,j}$ 初始化为 $i\times j$，$f_{W_{i},H_{i}}$ 初始化为 $0$。

枚举每块矩形可以划分成的两块子矩形，用子矩形的和的最小值更新 $f_{i,j}$。

因为可以横着划分也可以竖着划分，所以时间复杂度为 $O(W\cdot H\cdot(W+H))$。

代码：

#include <iostream>
const int MAXN = 605;
using namespace std;
int w, h, n;
int f[MAXN][MAXN];
int main() {
	ios::sync_with_stdio(false);
	cin >> w >> h;
	for (int i = 1; i <= w; ++i) {
		for (int j = 1; j <= h; ++j) {
			f[i][j] = i * j;
		}
	}
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int wi, hi;
		cin >> wi >> hi;
		f[wi][hi] = 0;
	}
	for (int i = 1; i <= w; ++i) {
		for (int j = 1; j <= h; ++j) {
			for (int k = 1; k <= i; ++k) {
				f[i][j] = min(f[i][j], f[k][j] + f[i - k][j]);
			}
			for (int k = 1; k <= j; ++k) {
				f[i][j] = min(f[i][j], f[i][k] + f[i][j - k]);
			}
		}
	}
	cout << f[w][h] << endl;
	return 0;
}