题目链接：P10977 Cut the Sequence - 洛谷。
本题是经典 DP 单调队列优化题型。
题目描述
给定一个长度为 $N$ 的整数序列 $\set{a_N}$，你需要将这个序列划分成若干部分，满足每一部分都是原序列的一个连续子序列，且每个部分的整数之和均不超过 $M$。你的任务是求出在所有合法的划分方式中，每一部分的最大值之和的最小值。
输入格式
输入的第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 10^5$，$1\le M < 2^{31}$）。第二行包含 $N$ 个整数，依次为 $a_1,a_2,\dots,a_N$（$0\le a_i\le 10^6$）。
输出格式
输出一个整数，表示每一部分的最大值之和的最小值。如果不存在合法的划分方式，输出 $-1$。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
说明/提示
样例解释：
将序列划分为三个部分：$\set{2,2,2},\set{8,1,8},\set{2,1}$，此时每一部分的最大值之和为 $2+8+2=12$。可以证明，不存在更优的方案。
题解
状态定义和转移
令 $f(i)$ 表示前 $i$ 个元素合法划分的最大值之和的最小值。很容易得到状态转移方程： $$ f(i) = \min_{0 \le j < i \land \sum_{k=j+1}^{i} a_k \le M}\set{f(j) + \max_{j < k \le i}\set{a_k}} $$ 即使我们使用 $O(1)$ 的复杂度来预处理 $a_k$ 的最大值，整个状态转移空间仍然是 $\Theta(n^2)$ 级别。
单调队列优化
很容易发现，$f(i)$ 是单调不减的。这意味着，如果 $a_j \le a_{j+1}$，则 $$ f(j-1) + \max_{j-1 < k \le i}\set{a_k} \le f(j) + \max_{j < k \le i}\set{a_k} $$ 因此，在队列中后加入的 $j+1$ 一定不会是一个比 $j$ 更优的决策。我们可以用单调队列来维护这一决策单调性。
