先倒序处理（为什么下文会说），然后就变成了划分尽量多的段，使得每段的和单调不减
很容易设置出一个状态\(f[i][j]\)表示前\(i\)堆草，最后一段是\([j,i]\)的最大高度，方程也很容易推导，但是时空复杂度显然炸掉
那么此时我们就应该思考，要么就是利用数组值来搞一些事情，要么就是发现某些引理（一般用贪心）
我们这里就可以想，对一个前\(i\)堆草来说，假设能堆到最高高度的方案有若干种，那么我们想要哪一种呢？显然是想要最后一段最小的一种，根据决策包容性易证
于是可以设\(f[i]\)表示前\(i\)堆草能够堆到的最大高度，\(g[i]\)表示所有最大高度的方案中最后一段最小的一种方案的最后一段的长度，\(s[i]\)表示前缀和，于是就有
\[f[i]=max_{j<i,s[i]-s[j]≥g[j]}(f[j])+1 \]这个时候我们倒序处理的原因就来了。对上面这个式子，看起来有两个条件要满足（在满足\(max(f[j])\)最大的情况下让\(j\)最大）导致需要使用数据结构优化DP，其实当\(j\)最大的时候\(f[j]\)也一定是最大的，因为\(f\)是单调不减的（我们倒序处理了，现在是让每段的和单调不减，由贪心的决策包容性，如果后面有若干堆草，我们至少可以直接放在最后一段来符合题意而且段数是一样的）
然后这个时候我们就可以用单调队列解决问题了
标签：最大,一段,干草堆,堆草,倒序,单调 From： https://www.cnblogs.com/dingxingdi/p/18004989