自动搬运

查看原文

来自洛谷，原作者为

	emptysetvvvv 这里埋葬着一位 OIer 的青春

搬运于2025-08-24 22:05:37，当前版本为作者最后更新于2019-08-26 19:02:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

单调队列 动态规划

背景

小萌新 $\varnothing$ 初遇此题是在模拟赛上，私以为数据很水，果断贪心.......

思路

• 贪心的错误性

相信很多人看到此题会想到贪心：让高层尽可能的小，从后往前倒叙贪心。

方面起见，我们倒叙读入，从前向后贪心使每段尽可能的小。

那么可以枚举 第一层由 $a[1]\sim a[i]$ 构成，设从前往后到了 $a[i]$，当前层的宽度为 $w$，那么就从 $i$ 再往前后连续一段，使得这一段的长度恰好大于 $w$。

对 $a[i]$ 求前缀和 $s[i]$，也就有了以下的代码：

for(int i = 1; i <= n and s[i]*ans <= s[n]; ++i) {
	int w = s[i], cur = i, pre, cnt = 1;
	while(s[cur] + w <= s[n]) { 
		pre = cur; 
		cur = lower_bound(s+cur+1, s+n+1, s[cur]+w) - s;
		w = s[cur] - s[pre];
		++cnt;
	} 
	ans = max(ans, cnt);
}

对于随机数据还是表现很不错的，但随手卡一下就会挂掉。

举个例子：

6
9 8 2 1 5 5 

倒叙之后是 $5\ 5\ 1\ 2\ 8\ 9$，贪心划分结果为 $5\ |\ 5\ |\ 1\ 2\ 8\ 9$ 共三层，然而正确答案是 $5\ |\ 5\ 1\ 2\ |\ 8\ |\ 9$ 共四层。

可以看出，贪心错误之处在于 前面的贪心使得 底层过大，难以扩展。

我们大胆猜测，有一个较为贪心的结论：

构成最优解的若干种方案中，一定有一种满足底层最小，即 底层最小的方案 一定可以 构造出最高的层数。

此结论由 ZKW 大神严谨证明。

• 考虑动态规划

一样，我们先把 $a$ 数组翻转过来，前缀和为 $s[i]$。

$f[i]$ 表示 考虑到位置 $i$ 时，$a[1]\sim a[i]$ 最高能搭多少层，$g[i]$ 表示此时最后一层（即 $a[i]$ 所在层）的最小宽度。

转移方程：

$$f[i]=f[j]+1(\text{ $j$ 为满足 } j\in[0,i-1]\text{ 且 } g[j]\leqslant s[i]-s[j] \text{的最后一个 }j) $$

要求最后一个 $j$ 是由于我们想要此时最后一层的宽度尽可能的小，得到 $j$ 后有 $g[i]=s[i]-s[j]$，

边界条件 $f[0]=0$。

转移复杂度 $O(n)$，总复杂度 $O(n^2)$。

• 考虑单调队列优化

转移条件为 $g[j]\leqslant s[i]-s[j]$，即 $g[j]+s[j]\leqslant s[i]$，那么就会有一个显然的结论：

若有 $k<j$ 且 $g[k]+s[k]\geqslant g[j]+s[j]$，则 $k$ 永远不可能再转移别人了，因为如果 $k$ 满足转移条件，那么 $j$ 也会满足，而 $j$ 的位置还更加靠后。

因此，我们可以维护一个 $g+s$ 值单调递增的 单调队列。

每次转移时从 单调队列中找到 最后一个 $g[j]+s[j]\leqslant s[i]$ 的位置 $j$，单调队列中 $j$ 以左的元素从队首出队。

转以后从队尾弹出 $g[j]+s[j]\geqslant g[i]+s[i]$ 的元素，然后将位置 $i$ 加入单调队列。

每个元素进出队列各一次，复杂度 $O(n)$。

代码

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100005;
int n, a[maxn], s[maxn], f[maxn], g[maxn];
int q[maxn], l, r;
int main() {
	scanf("%d", &n);
	for(int i = n; i; --i) scanf("%d", a+i);
	for(int i = 1; i <= n; ++i) s[i] = s[i-1] + a[i];
	for(int i = 1; i <= n; ++i) {
		while(l < r and s[q[l+1]]+g[q[l+1]] <= s[i]) ++l;
		f[i] = f[q[l]] + 1;
		g[i] = s[i] - s[q[l]];
		while(l < r and s[q[r]]+g[q[r]] >= s[i]+g[i]) --r;
		q[++r] = i;
	}
	printf("%d\n", f[n]);
	return 0;
}