题目描述

奶牛们讨厌黑暗。

为了调整牛棚顶的电灯的亮度，Bessie 必须建一座干草堆使得她能够爬上去够到灯泡。

一共有 $N$ 大包的干草（从 $1$ 到 $N$ 编号）依靠传送带连续的传输进牛棚来。

第 $i$ 包干草有一个宽度 $W_i$。

所有的干草包的厚度和高度都为 $1$。

Bessie 必须利用所有 $N$ 包干草来建立起干草堆。

她可以想放多少包就放多少包来建立起草堆的地基（当然是紧紧的放在一行中）。

接下来她可以将下一个草包放在之前一级的上方来建立新的一级。

注意：每一级不能比下面的一级宽。

她持续的这么放置，直到所有的草包都被安置完成。

她必须按照草包进入牛棚的顺序堆放草包。

说得更清楚一些：一旦她将一个草包放在第二级 ，那么她不能将接下来的草包放在第一级上。

Bessie 的目标是建立起最高的草包堆。

输入格式

第 1 行：一个整数 $N$。

第 2..N+1 行：第 $i+1$ 行包含整数 $W_i$。

输出格式

输出一个整数，表示草包堆的最高的高度。

样例

3
1
2
3

2

样例解释

干草包顺序

$N = 3$
宽度依次为：$W_1 = 1$, $W_2 = 2$, $W_3 = 3$

可能的堆法

必须按照顺序 $1, 2, 3$ 使用所有干草包。

尝试 1：
第一级：放 1 和 2（宽度和为 3），第二级：放 3（宽度为 3）。
但第二级宽度（3）等于第一级宽度（3），违反了“每一级不能比下面的一级宽”的规则（应该是严格小于吗？题目说“不能比下面的一级宽”，即宽度应 ≤ 下面一级，但通常理解为不能更宽，即 ≤ 下面一级。但样例中宽度相等似乎不允许）。
检查样例：第一级宽度 3，第二级宽度 3，相等，那么高度为 2。这似乎是允许的？但题目描述中说“不能比下面的一级宽”，相等是允许的。

尝试 2：
第一级：放 1（宽度 1），第二级：放 2（宽度 2），但 2 > 1，违反了“不能比下面的一级宽”。
所以不行。

尝试 3：
第一级：放 1 和 2 和 3（宽度和 6），只有一级，高度为 1。
高度较低。

尝试 4：
第一级：放 1 和 2（宽度和 3），第二级：放 3（宽度 3）。
高度为 2，且第二级宽度等于第一级宽度，不违反规则（因为“不能比下面的一级宽”意味着可以等于）。

因此最高高度为 2。

数据范围

• $1 \le N \le 100000$
• $1 \le W_i \le 10000$

问题分析

这是一个动态规划问题。

题意再梳理

• 给定一个序列 $W_1, W_2, \dots, W_N$。
• 要将序列划分成若干连续段（每段对应一层），从底层到顶层依次对应序列的前缀到后缀。
• 要求：从上往下看（即从序列的后面往前面），每一层的总宽度不大于下一层的总宽度。
• 目标：最大化层数（高度）。

换句话说，我们需要将序列从后往前划分成若干段，使得段和的序列非严格递增（从顶到底）。

动态规划思路

设 $f[i]$ 表示将后缀 $[i, n]$ 划分成若干层，且**第一层（即最顶层）**的宽度最小是多少，同时在这种情况下能获得的最大高度。

或者更直接地： 设 $dp[i]$ 表示从 $i$ 到 $n$ 能堆的最大高度，$g[i]$ 表示在这种情况下，最顶层（即第一层）的最小可能宽度。

转移时，我们考虑下一层（即更下面一层）从 $j$ 开始（$j > i$），那么当前层就是 $[i, j-1]$，宽度和为 $sum(i, j-1) = S_{j-1} - S_{i-1}$（其中 $S$ 是前缀和）。

要求：

1. $sum(i, j-1) \le g[j]$（当前层宽度不大于下一层宽度）
2. 在满足条件 1 的 $j$ 中，选择能使高度最大的，即 $dp[i] = dp[j] + 1$。
3. 如果有多个 $j$ 能使高度相同，则选择使当前层宽度 $sum(i, j-1)$ 最小的，作为 $g[i]$。

优化

直接转移是 $O(N^2)$，会超时。

可以观察到，最优的 $j$ 是满足 $sum(i, j-1) \le g[j]$ 且 $j$ 尽量小的位置。因为 $sum(i, j-1)$ 随 $j$ 增大而增大，$g[j]$ 随 $j$ 变化有某种单调性。

更高效的解法是： 从后往前维护一个决策队列，队列中的元素 $(j, g[j], dp[j])$ 满足 $g[j]$ 单调递增（因为从后往前，越靠后的位置，其顶层宽度应该越小才能让前面的层放上去）。

对于当前 $i$，我们需要找到最小的 $j > i$ 使得 $sum(i, j-1) \le g[j]$。由于 $sum(i, j-1) = S_{j-1} - S_{i-1}$，移项得 $S_{i-1} \ge S_{j-1} - g[j]$。

因此我们可以维护一个关于 $S_{j-1} - g[j]$ 的单调队列，每次取队首满足条件的 $j$ 作为转移点。

这样可以在 $O(N)$ 时间内解决。

实现提示

1. 计算前缀和 $S$。
2. 从 $n$ 到 $1$ 倒序计算。
3. 初始：$dp[n+1] = 0$, $g[n+1] = 0$（虚拟位置）。
4. 用单调队列维护可能的 $j$，满足 $S_{j-1} - g[j]$ 单调递减（这样队首的 $S_{j-1} - g[j]$ 最大，更容易满足 $S_{i-1} \ge S_{j-1} - g[j]$）。
5. 对于每个 $i$，从队首弹出不满足条件的元素（即 $S_{i-1} < S_{j-1} - g[j]$），最后一个被弹出的元素就是最优的 $j$（因为队列按 $j$ 递增，$S_{j-1} - g[j]$ 递减，最后一个满足条件的 $j$ 就是最小的 $j$ 使得 $S_{i-1} \ge S_{j-1} - g[j]$）。
6. 更新 $dp[i]$ 和 $g[i]$，然后将 $i$ 加入队列。

最终答案

输出 $dp[1]$。