Description
奶牛们讨厌黑暗。 为了调整牛棚顶的电灯的亮度，Bessie必须建一座干草堆使得她能够爬上去够到灯泡 。一共有N大包的干草（1<=N<=100000）(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个 宽度W_i(1<=w_i<=10000)。所有的干草包的厚度和高度都为1. Bessie必须利用所有N包干草来建立起干草堆，并且按照他们进牛棚的顺序摆放。她可以相放多少包就放 多少包来建立起tower的地基（当然是紧紧的放在一行中）。接下来他可以放置下一个草包放在之前一级 的上方来建立新的一级。注意：每一级不能比下面的一级宽。她持续的这么放置，直到所有的草包都被安 置完成。她必须按顺序堆放，按照草包进入牛棚的顺序。说得更清楚一些：一旦她将一个草包放在第二级 ，她不能将接下来的草包放在地基上。 Bessie的目标是建立起最高的草包堆。
Input
第1行：一个单一的整数N。 第2~N+1行：一个单一的整数:W_i。
Output
第一行：一个单一的整数，表示Bessie可以建立的草包堆的最高高度。
Sample Input
3
1
2
3
Sample Output
2
输出说明：
前两个（宽度为1和2的）放在底层，总宽度为3，在第二层放置宽度为3的。
+----------+
| 3 |
+---+------+
| 1 | 2 |
+---+------+
Solution
要猜一个神仙结论才能优化(dp)，否则写到死也是(n^2)的...。
结论：一定存在一种方案，在保证层数最高的同时，底层宽度最小。证明引用zkw的：
任意取出一个能使层数最高的方案，设有CA层，把其中从下往上每一层最大的块编号记为Ai；任取一个能使底边最短的方案，设有CB层，把其中从下往上每一层最大的块编号记为Bi。
显然A1>=B1,ACB<=BCB，这说明至少存在一个k属于(1,CB)，满足Ak-1>=Bk-1且Ak<=Bk。也就是说，方案 A 第K 层完全被方案 B 第K 层包含。
构造一个新方案，第K 层往上按方案 A，往下按方案 B，两边都不要的块放中间当第K 层。新方案的层数与 A 相同，而底边长度与 B 相同。
证毕。
那么现在问题就转化为了倒推，然后要找一个编号最小的点(j)，满足(s[j-1]-s[i-1]>=f[j])。这个可以单调队列维护(f[j]-s[j-1])的(min)即可。弹出队头的话需要更改一下，因为肯定要选一个合法的答案，所以要先看(l+1)这个位置可不可行，如果可行就弹出队头（因为要找到的是满足条件的，编号最小的点(j)，而我们是倒着把点放进单调队列的，所以要找单调队列中最后一个满足条件的点(j)来转移）。复杂度(O(n))
#include <bits/stdc++.h>
using namespace std;
namespace io {
char buf[1<<21], *p1 = buf, *p2 = buf;
inline char gc() {
if(p1 != p2) return *p1++;
p1 = buf;
p2 = p1 + fread(buf, 1, 1 << 21, stdin);
return p1 == p2 ? EOF : *p1++;
}
#define G gc
#ifndef ONLINE_JUDGE
#undef G
#define G getchar
#endif
template<class I>
inline void read(I &x) {
x = 0; I f = 1; char c = G();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = G(); }
while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = G(); }
x *= f;
}
template<class I>
inline void write(I x) {
if(x == 0) {putchar('0'); return;}
I tmp = x > 0 ? x : -x;
if(x < 0) putchar('-');
int cnt = 0;
while(tmp > 0) {
buf[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while(cnt > 0) putchar(buf[--cnt]);
}
#define in(x) read(x)
#define outn(x) write(x), putchar('
')
#define out(x) write(x), putchar(' ')
} using namespace io;
#define ll long long
const int N = 100010;
int n, a[N], f[N], g[N], s[N], q[N];
int main() {
read(n);
for(int i = 1; i <= n; ++i) read(a[i]), s[i] = s[i - 1] + a[i];
int l = 1, r = 1;
q[1] = n + 1;
for(int i = n; i; --i) {
while(l < r && s[q[l + 1] - 1] - s[i - 1] >= f[q[l + 1]]) ++l;
f[i] = s[q[l] - 1] - s[i - 1]; g[i] = g[q[l]] + 1;
while(l < r && f[i] - s[i - 1] < f[q[r]] - s[q[r] - 1]) --r;
q[++r] = i;
}
outn(g[1]);
}