题意
给定序列 \(a_1,a_2,\cdots,a_n\) ，将其划分为若干段，要求子段和单调不增，求最大段数。
数据范围：\(1\le n\le 10^5,1\le a_i\le 10^4\) 。
题解
考虑逆推。问题转化为：
给定序列 \(a\) ，将其划分为若干段，使子段和单调不减。
我们记 \(f_i\) 表示前 \(i\) 个元素能划分成的最大段数。
可以注意到一条性质：\(f\) 单调不减。
考虑 \(f_i\) 对应的划分方案，在此基础上直接把 \(a_{i+1}\) 丢到最后一个子段里，段数不变。于是显然有 \(f_{i+1}\ge f_i\) 。
事实上，如果我们一开始就顺推的话，这个性质就不成立了。
比如 \(3,2,1\) 可以分成 \(3\) 段，但是 \(3,2,1,114514\) 只能分成一段。
本质上是因为 \(a_i>0\) 的条件破坏了对称性，使得逆推做法变容易了，但是对顺推没有帮助。
这也是本题要逆推的原因。
回到原题，易知转移方程为 \(\displaystyle f_i=\max_{1\le j<i}\{f_j+1\}\) 。其中 \(j\) 还要满足一个与子段和有关的约束条件。
为了写出这个约束条件，我们设：
\(s_i\) 表示前缀和 \(a_1+\cdots+a_i\) 。
\(g_i\) 表示 \(f_i\) 对应的划分方案中，最后一个子段的元素和。
那么约束条件就是 \(g_j\le s_i-s_j\) 。
容易发现，对于同一个 \(f_j\) ，我们希望 \(g_j\) 最小。
转移之后得到的 \(g_i\) 值为 \(s_i-s_j\) ，我们希望它最小。也就是 \(s_j\) 最大，也就是 \(j\) 最大。
此外，由于 \(f\) 单调不减，\(j\) 最大时 \(f_j\) 也是最大的，那么此时的转移一定是最优解。
至此可以写出最终的转移方程：\(\begin{cases}f_i=f_j+1\\g_i=s_i-s_j \end{cases}\) ，其中 \(j<i,g_j+s_j\le s_i\) ，且 \(j\) 取最大值。
直接实现的话是 \(O(n^2)\) 的，还不能得到满分。
但再稍微思考一下就会发现，这个 dp 可以很方便地加上一个单调队列优化，然后就变成 \(O(n)\) 的了，就过掉了。
代码
View Code
#include<stdio.h>
const int N=1e5+5;
int n,l,r,a[N],s[N],f[N],gs[N],Q[N];
int main() {
scanf("%d",&n);
for (int i=1; i<=n; ++i)
scanf("%d",a+i);
for (int i=n; i; --i) {
s[i]=s[i+1]+a[i];
while (l<r&&gs[Q[l+1]]<=s[i]) ++l;
f[i]=f[Q[l]]+1,
gs[i]=(s[i]<<1)-s[Q[l]];
while (l<=r&&gs[i]<=gs[Q[r]]) --r;
Q[++r]=i;
}
printf("%d\n",f[1]);
return 0;
}