自动搬运

查看原文

来自洛谷，原作者为

	_xbn 今天这个地区是晴天，昨天我一整天都很享受

搬运于2025-08-24 22:07:05，当前版本为作者最后更新于2021-05-18 20:15:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

很显然此题要用动态规划，我们设 $f(i)$ 表示当前到第 $i$ 本书， 书架的最小高度。

接下来考虑转移，转移我们可以分两种情况讨论，第一，对于当前这本书，我们要新开一个书架，那么 $f(i) = f(i-1) + h(i)$，第二，我们选择把当前这本书插入之前的书架，那么我们就要知道前面书的最大高度，我们可以开一重循环寻找之前的最大高度，用它来更新当前状态 $f(i) = min(f(i),f(j-1) + maxn)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 2002;
int n, m, p, k, ans, sum, tot, cnt, a[N], b[N], f[N], c[N], l;
int main()
{
	std::cin>> n >> l;
	for(int i = 1; i <= n; i++)
	{
		std::cin >> a[i] >> b[i];
		c[i] = c[i - 1] + b[i];
		f[i] = 1e9;
	}
	for(int i = 1; i <= n; i++)
	{
		f[i] = f[i - 1] + a[i];
		tot = a[i];
		for(int j = i - 1; j >= 1; j--)
		{
			if(c[i] - c[j - 1] > l)break;
			tot = max(tot, a[j]);
			f[i] = min(f[i], f[j - 1] + tot);
		}
	}
	cout << f[n];
	return 0;
}