P10977 Cut the Sequence

本题是经典 DP 单调队列优化题型。

题目描述

给定一个长度为 $N$ 的整数序列 ${a_{N}}$ ，你需要将这个序列划分成若干部分，满足每一部分都是原序列的一个连续子序列，且每个部分的整数之和均不超过 $M$ 。你的任务是求出在所有合法的划分方式中，每一部分的最大值之和的最小值。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$ （ $1 \leq N \leq 10^{5}$ ， $1 \leq M < 2^{31}$ ）。第二行包含 $N$ 个整数，依次为 $a_{1}, a_{2}, \dots, a_{N}$ （ $0 \leq a_{i} \leq 10^{6}$ ）。

输出格式

输出一个整数，表示每一部分的最大值之和的最小值。如果不存在合法的划分方式，输出 $- 1$ 。

输入输出样例 #1

输入 #1

1 2	`8 17 2 2 2 8 1 8 2 1`

输出 #1

说明/提示

样例解释：

将序列划分为三个部分： ${2, 2, 2}, {8, 1, 8}, {2, 1}$ ，此时每一部分的最大值之和为 $2 + 8 + 2 = 12$ 。可以证明，不存在更优的方案。

题解

状态定义和转移

令 $f (i)$ 表示前 $i$ 个元素合法划分的最大值之和的最小值。很容易得到状态转移方程：

f (i) = min_{0 \leq j < i \land \sum_{k = j + 1}^{i} a_{k} \leq M} {f (j) + max_{j < k \leq i} {a_{k}}}

即使我们使用 $O (1)$ 的复杂度来预处理 $a_{k}$ 的最大值，整个状态转移空间仍然是 $Θ (n^{2})$ 级别。

单调队列优化

很容易发现， $f (i)$ 是单调不减的。这意味着，如果 $a_{j} \leq a_{j + 1}$ ，则

f (j - 1) + max_{j - 1 < k \leq i} {a_{k}} \leq f (j) + max_{j < k \leq i} {a_{k}}

因此，在队列中后加入的 $j + 1$ 一定不会是一个比 $j$ 更优的决策。我们可以用单调队列来维护这一决策单调性。