BZOJ 1233
题意：给出$n$个数，将这$n$个数按顺序分组，并且每一组都不能比前面一组和大。求最大能分几组。
引理：
在多种可行的堆叠方案中，至少有一种能使层数最高的方案同时使得底边最短。
即底边最短的，层数一定最高。
证明略去。可以感性认为底边越短，层数就能堆得越高。
所以可以设$dp(i)$为$[i,n]$的最小底边长度，$g(i)$为其层数，$\operatorname{sum}$为$n$个数前缀和。
则
$$
dp(i)=\min_{i < j \leq n, dp(j)\leq \operatorname{sum}(j - 1) - \operatorname{sum}(i - 1)}(\operatorname{sum}(j - 1) - \operatorname{sum}(i - 1))
$$
最小的$j$更优，因为$\operatorname{sum}$的单调性。
将条件$dp(j)\leq \operatorname{sum}(j - 1) - \operatorname{sum}(i - 1)$转化为$\operatorname{sum}(j - 1) - dp(j)\geq \operatorname{sum}(i - 1)$
则如果存在$k < j$，且
$$
\operatorname{sum}(k - 1) - dp(k) > \operatorname{sum}(j - 1) - dp(j)
$$
则$j$为无用决策。单调队列维护。
单调队列左端点维护最小的$\operatorname{sum}(j - 1) - dp(j)\geq \operatorname{sum}(i - 1)$
右端点维护$\operatorname{sum}(j - 1) - dp(j)$递减
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL n, w[100000 + 5], sum[100000 + 5];
LL f[100000 + 5], g[100000 + 5], q[100000 + 5];
void clean() {
ms(sum, 0), ms(f, 0), ms(g, 0);
}
int solve() {
clean();
scanf("%lld", &n);
for (LL i = 1; i <= n; ++i) scanf("%lld", &w[i]), sum[i] = sum[i - 1] + w[i];
LL l = 1, r = 1;
q[1] = n + 1;
for (LL i = n; i; --i) {
while (l < r && sum[q[l + 1] - 1] - f[q[l + 1]] >= sum[i - 1]) ++l;
f[i] = sum[q[l] - 1] - sum[i - 1];
g[i] = g[q[l]] + 1;
while (l <= r && sum[i - 1] - f[i] >= sum[q[r] - 1] - f[q[r]]) --r;
q[++r] = i;
}
printf("%lld\n", g[1]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
