单调队列

优化多重背包

直接做的时间复杂度是 $O(W \sum k_i)$，不好。我们希望能做到 $O(nW)$。

考虑对于每一个 $i$，优化 $f_i$ 这一层的转移。设 $j = w_i x + y$（$0 \le y < w_i$），令 $g_{i,x,y} = f_{i, w_i x + y}$。

设 $G_{x,y} = g_{i-1,x,y} - v_i \times x$，则

注意到，对于固定的 $y$，可以通过单调队列计算，时间复杂度 $O(\frac W {w_i})$。而 $y$ 总共有 $w_i$ 个，因此每个物品 $i$ 的计算的时间复杂度为 $O(\frac W {w_i} \times w_i) = O(W)$，总时间复杂度 $O(n W)$。

单调队列 例题

P2254 [NOI2005] 瑰丽华尔兹 (Easy)

$f_{i,x,y}$ 第 $i$ 个时刻在 $(x,y)$ 的最长路程

$f_{i,x,y} = \max(f_{i-1, \text{last}(x,y)}, f_{i-1,x,y})$

$f_{i,x,y}$ 第 $i$ 个时间段内在 $(x,y)$ 的最长路程

$O(n^4)$

TODO:

决策单调性

对于一个 DP 式子

令 $p_i$ 为 $i$ 的最优决策点（即 $\min$ 改成 $\arg \min$ 的结果），而且是最小的。有时也记作 $\text{opt}(i)$。若 $p_i$（非严格）单调，则 $f$ 具有决策单调性。

接下来我们看决策单调性如何优化 DP。

决策单调性优化 DP：分治

已知 $[l,r]$ 的最优决策在 $[L,R]$ 上。求出 $f_{mid}$ 的最优决策 $p_{mid}$，可知 $[l,mid-1]$ 的最优决策在 $[L, p_{mid}]$，$[mid+1, r]$ 的最优决策在 $[p_{mid}, R]$。带 1log。

决策单调性优化 DP：队列 + 二分

如果 $a_j$ 依赖于 $f_j$ 怎么办？

此时分治的“离线”做法失效，我们需要一个按顺序的做法。

这个做法也带 1log，功能上完爆分治，但是麻烦很多。所以能分治还是分治吧。

考虑一个位置 $j$，使得 $p_x = j$ 的 $x$ 应该是一个区间 $[l, r]$。

建立一个存储三元组 $(j, l, r)$ 的队列。

每次到一个位置 $i$ 时判断 $r \ge i$，如果不满足则已经过时，弹掉。

TODO:

四边形不等式

一个二元函数 $w(l,r)$（定义域 $l \le r$），若对于任意 $l_1 \le l_2 \le r_1 \le r_2$，有：

则 $w$ 满足四边形不等式。

感性记忆：画一个横轴是 $l$ 纵轴是 $r$ 的坐标系，四个坐标构成一个矩形，主对角线方向上的两个点值之和小于副对角线方向上的两个点值之和。

目前看起来这个不等式有些莫名其妙，后面将从偏导数的角度说明这个性质为什么是“自然的”。

特别地，若等号永远取到，我们称 $w$ 满足四边形恒等式，对应偏导数那段中二阶混合偏导恒等于 $0$ 的情形。

具体推式子时，可以看作“调换 $r_1, r_2$”的功能。

判定决策单调性

对于

定理：若 $w$ 满足四边形不等式，则 $f$ 具有决策单调性。这给出了一个判定决策单调性的充分条件。

实用技巧：四边形不等式相对不太容易打表看出，所以考场上打表的时候打 $p$ 不要打 $w$。

证明

对于两个位置 $i < i’$，尝试证明 $p_i \le p_{i’}$。

$\forall j \in [0, p_i)$，

（最优决策点的定义）

$j \le p_i \le i \le i’$，因此

（$w$ 符合四边形不等式）

两个不等式相加，整理得：

对于 $i’$ 的决策，选择小于 $p_i$ 的任意 $j$ 都不优，因此 $p_{i’}$ 必须在 $p_i$ 及以后，得证。

💡偏导数视角的理解

仅限于 $w$ 是连续函数的情况，而且需要 $w$ 性质好（指可以多次求导）。

令下标表示偏导数。$w_{lr}(x,y)$ 表示 $\frac {\partial^2} {\partial l \partial r} w(x,y)$。

若

处处成立，则四边形不等式成立：

而且是充分的，可以通过泰勒展开证明（保留二阶项，最终只有 $w_{lr} \Delta l \Delta r$ 这一项会留下）。

四边形不等式万能判定定理

名字乱起的。

本质是只要对于任意单位正方形都满足四边形不等式，就可以对任意矩形通过数学归纳证明。

若对于任意 $x < y$，$x \le x+1 \le y \le y+1$ 四个点满足四边形不等式（即 $\Delta_l \Delta_r w(x,y) \le 0$），则 $w$ 满足四边形不等式。

感性理解：是 $\frac {\partial^2} {\partial l \partial r} w(x,y) \le 0$ 的离散版本。

区间包含单调性

若二元函数 $w(l,r)$（定义域 $l \le r$）满足 $\forall l_1 \le l_2 \le r_1 \le r_2$ 有

则 $w$ 具有区间包含单调性。

四边形不等式与区间包含单调性常见判定定理

• 两个函数 $w_1$ 和 $w_2$ 都满足四边形不等式，则 $\forall c_1, c_2 \ge 0$，$c_1 w_1 + c_2 w_2$ 也满足四边形不等式。
• 若存在函数 $f,g$ 使得 $w(l,r) = f(r) - g(l)$，则 $w$ 满足四边形恒等式。
  • 特别地，当 $f,g$ 均（非严格）单调递增时，$w$ 满足区间包含单调性。
• 设 $h(x)$ 是一个单调递增的凸函数（下凸），若 $w$ 同时满足四边形不等式和区间包含单调性，则 $h(w)$ 也同时满足四边形不等式和区间包含单调性。
• 设 $h(x)$ 是一个凸函数（下凸），若 $w$ 同时满足四边形恒等式和区间包含单调性，则 $h(w)$ 也满足四边形不等式。

前两条非常平凡，后两条提供一个感性理解：

四边形不等式提供了 $w_{lr} \le 0$（如果是四边形恒等式则提供了 $w_{lr} = 0$，此时我们不关心 $h’$）；区间包含单调性提供了 $w_l \le 0$ 和 $w_r \ge 0$；凸函数提供了 $h’’ \ge 0$；如果 $h$ 单调递增则还提供了 $h’ \ge 0$。

而区间包含单调性则更为简单：

$w_l \le 0$，$h’ \ge 0$，显然最终 $\le 0$。$r$ 的情况也是同理。

四边形不等式优化区间 DP

对于 DP 方程

若 $w$ 同时满足四边形不等式和区间包含单调性，则 $f$ 满足四边形不等式。后面会证明。

令 $\text{opt}(l,r)$ 为 $[l,r]$ 的最优决策点。

我们若把 $f_{k+1, r}$ 看作原来决策单调性式子中的 $w$，然后根据 $f$ 满足四边形不等式就可以推出 $f$ 满足决策单调性：$\text{opt}(l,r) \ge \text{opt}(l, r-1)$。

同理，把 $f_{l,k}$ 看作原来的 $w$，根据 $f$ 满足四边形不等式可以推出反向的决策单调性：$\text{opt}(l,r) \le \text{opt}(l+1,r)$。

$\text{opt}(l,r) \in [\text{opt}(l,r-1), \text{opt}(l+1,r)]$，在这个范围内枚举 $f_{l,r}$ 的转移点即可。接下来说明时间复杂度。

因此时间复杂度为 $O(n^2)$。

证明 $f$ 满足四边形不等式

我们想要证明

考虑按 $r_2 - l_1$ 归纳。显然边界 $l_1 = l_2$ 或 $r_1 = r_2$ 显然成立。

令 $o = \text{opt}(l_1, r_2)$。

Case I：若 $o \in [l_1, l_2)$ 或者 $o \in [r_1, r_2)$。注意到这两种情况本质相同，仅考虑后者的证明。

考虑反推

对上了，再用一次区间包含单调性 $w(l_2, r_2) \le w(l_1, r_2)$ 即可。

Case II：$o \in [l_2, r_1)$。思路是一样的，所以这次直接顺推（实际上想的时候还是可以考虑逆推的，但是这里为了简洁就算了）。

令 $o_1 = o = \text{opt}(l_1, r_2)$，$o_2 = \text{opt}(l_2, r_1)$。

Ref

• 四边形不等式优化 - OI Wiki
• DP 优化方法大杂烩 II. - qAlex_Weiq - 博客园
• DP的决策单调性优化总结 - command_block
• 【学习笔记】动态规划—斜率优化DP（超详细） - 辰星凌

四边形不等式 例题

P3515 [POI 2011] Lightning Conductor

给定长为 $n$ 的序列 $a$，对于每个 $i \in [1,n]$，求出 $ans_i = \lceil \max\limits_{j=1}^n(a_j + \sqrt{\lvert i - j \rvert}) \rceil - a_i$。

$n \le 5 \times 10^5$。

首先分类讨论 $i - j$ 的正负，两边做法完全一样，接下来只考虑 $i - j > 0$ 的情况。

要求的这个东西和上面讲的决策单调性几乎一样，我们先转成 $\min$：

我们希望知道 $- \sqrt{i - j}$ 是否满足四边形不等式。

因此 $ans$ 满足决策单调性，分治 $O(n \log n)$ 可以解决。

第二个证明：如果利用前面说的性质来判定四边形不等式会更方便。首先 $r - l$ 是满足四边形恒等式的，因为可以写成关于 $r$ 和 $l$ 的函数的线性组合。然后 $f(x) = - \sqrt x$ 是一个凸函数，所以它们的复合 $- \sqrt{r - l}$ 满足四边形不等式。

P1912 [NOI2009] 诗人小G

将长为 $n$ 的数列 $a$ 分为若干段，再给定常数 $k,p$。

每一段 $[l,r]$ 的权值为：

\[w(l,r) = \left\lvert \sum\limits_{k=l}^r a_k - L \right\rvert^p\]

求出一个任意方案使得所有段权值之和最小。

$n \le 10^5$，$L \le 3 \times 10^6$，$1 \le p \le 10$，$1 \le a_i \le 30$。

首先把 $w$ 写成前缀和 $w(l,r) = \lvert s_r - s_{l-1} - L \rvert^p$。

接下来证明 $w$ 满足四边形不等式。万能判定定理是可以做的，但是需要分类讨论和二项式展开非常麻烦。我们首先注意到 $s_r - s_{l-1} - L$ 满足区间包含单调性和四边形恒等式，而 $f(x) = \lvert x \rvert^p$ 在 $p \ge 1$ 时时是凸函数，因此 $w(l,r)$ 满足四边形不等式。

由于这题带依赖，只能使用二分 + 单调队列做法 $O(n \log n)$ 解决。

P4767 [IOI 2000] 邮局 加强版 (Lunatic)

TODO:

WQS 二分的做法见《动态规划 3》一文。

$f_{i,j}$ 为只考虑前 $j$ 个村庄，放 $i$ 个邮局的答案。

$f_{i,j} = \min\limits_{k=1}^j (f_{i-1,k-1} + w(k,j))$

可以证明 $w$ 满足四边形不等式。

$O(P V \log V)$。

斜率优化可以做 $O(PV)$。

TODO: $f$

💡P4954 [USACO09OPEN] Tower of Hay G

TODO:

TODO:

斜率优化

若一个 DP 可以被写为这样的形式：

（$\min$ 可以改成 $\max$）

则可以斜率优化。即，$w(i,j)$ 在剔除掉只有 $i$ 或者只有 $j$ 的项之后，能够写成 $i$ 的项乘上 $j$ 的项，必须是乘积而不是其它形式。

我们可以看成 $j \in [0,i)$ 的 $(x(j), y(j))$ 组成了一个二维坐标系的“点云”，每次查询的时候给定一个斜率 $k(i)$，过每个点作一条斜率为 $k(i)$ 的直线，并求出最小截距。

注意到，当 DP 式子是 $\min$ 时，这个点云上只有下凸壳会造成贡献。（同理 $\max$ 时只有上凸壳会造成贡献）具体对于凸包的维护以及查询方式将在后面阐述。

不难发现斜率优化解决的问题类型和决策单调性优化非常相似，但是斜率优化通过更特殊的 DP 式子有时可以获得更好的复杂度。

$k,x$ 都单调

TODO: 单调队列

$x$ 单调

TODO: 凸包上二分

都不单调

TODO: CDQ 分治

斜率优化 例题

P3195 [HNOI2008] 玩具装箱

（$x,k$ 都单调）

将长为 $n$ 的数列 $c$ 分为若干段，每一段 $[l,r]$ 的权值为：

\[w(l,r) = \left( \sum\limits_{i=l}^r c_i - L \right)^2\]

求最小权值和。

$n \le 5 \times 10^4$，$1 \le c_i,L \le 10^7$。（题意有修改）

依旧把 $w$ 写成前缀和形式：$w(l,r) = (s_r - s_{l-1} - L)^2$。动态规划式子为 $f_i = \min\limits_{j \in [0,i)}(f_{j} + w(j+1, i))$。

整理后可以得到：

拼出了斜率优化的形式。

注意到斜率 $k(i) = 2 (s_i - L)$ 单调递增，$x(j) = s_j$ 单调递增，可以使用单调队列维护。时间复杂度 $O(n)$。

P2900 [USACO08MAR] Land Acquisition G

（$x,k$ 都单调）

有 $n$ 个矩形，每个矩形大小为 $w_i \times l_i$。把这 $n$ 个矩形划分为若干个子集，每一个子集的权值为其中的最大长乘最大宽 $\max(w_i) \times \max(l_i)$。找到一个划分使得权值和最小，输出这个最小权值。

$n \le 5 \times 10^4$。

首先注意到被二维偏序掉的矩形不构成贡献。对于剩下的矩形，我们按 $w$ 从小到大排序，则 $l$ 必定从大到小排序。

很容易证明在现在的序列上，每个分组都是连续的一个区间。

DP：

一眼斜率优化，$k(i) = -w_i$ 单调递减，$x(j) = l_j$ 单调递减，可以单调队列优化，时间复杂度 $O(n)$。

CF311B Cats Transport

TODO:

TODO:

P5785 [SDOI2012] 任务安排

（$x$ 单调）

机器上有 $n$ 个需要处理的任务，它们构成了一个序列。这些任务被标号为 $1$ 到 $n$，因此序列的排列为 $1 , 2 , 3 \cdots n$。这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T_i$（可以为负）。在每批任务开始前，机器需要启动时间 $s$，而完成这批任务所需的时间是各个任务需要时间的总和。

注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。

请确定一个分组方案，使得总费用最小。输出这个总费用。

$n \le 3 \times 10^5$。

弱化版：P2365 任务安排

TODO:

P4027 [NOI2007] 货币兑换

$k,x$ 都不单调

TODO: 平衡树 / CDQ