决策单调性优化 dp 学习笔记

• first version is written on 2022.3.30
• updated on 2023.7.14：增加了例题，增加了二分栈板块。
• updated on 2023.7.20：增加了大量例题。注意很多题是可以一题多解的。

公式较多，加载不出来的话试试检查-长按刷新-硬刷新。

dp 这块的东西又多又杂，本来想把斜率优化或者 wqs 二分一起总结一下，但是难度实在有点大，所以还是按照专题慢慢来。

首先对决策单调性有一个整体的认识。

对于最优化 dp 而言，每个状态从若干个状态转移而来，其中存在一个最优转移点。dp 拥有决策单调性指的就是这个最优转移点按照某种顺序单调变化，例如从左到右等等。

四边形不等式

如何判断 dp 是否拥有决策单调性，在考场上我们不妨通过打表来进行检验，但如果需要严格证明的话，我们就需要用到四边形不等式。

在接下来的部分中，我们使用 $a \prec b$ 表示 $a$ 严格优于 $b$，类似的，$a\preceq b$ 表示 $a$ 不劣于 $b$。

在实际问题中，$\prec$ 很多时候指的是 $<$，但其也可能是 $>$，或者是别的用于衡量优劣的指标，请注意下面有些时候的 $\min$ 或者 $\infty$ 符号也是建立在 $\prec$ 规则上的。

重点都将粗体显示或者被包含在方框中，是值得重点注意的内容，也方便在本文中寻找某个公式的时候能够快速定位。

考虑一个实值函数 $C(l,r)\ (1\le l\le r\le n)$，我们称之为代价函数，其实际意义是区间 $[l,r]$ 的贡献或代价，对于 $a\le b\le c\le d$ 如果其满足

$$
\boxed{
\begin{array}{c}
\text{四边形不等式}\\
C(a,c)+C(b,d)\preceq C(a,d)+C(b,c)
\end{array}
}
$$

简单来说，交叉优于包含，我们就称这个代价函数满足四边形不等式，通常我们还要求满足

$$
C(b,c)\preceq C(a,d)
$$

这个性质被称作区间包含单调性，保证了对于一个区间而言，我们不可能在其中增加若干元素，然后使其变得更优，避免了一些反直觉的情况产生，后续的证明也需要用到这一性质。

对于满足四边形不等式的代价函数 $C(l,r)$，在区间 dp 部分中我们还要求其满足区间包含单调性，我们就称其是四边形友好的。

接下来，我们就可以将四边形不等式带入具体问题中，看看具体问题中的决策单调性。

无限制的序列分割问题

将序列分为若干段，最优化代价总和，用 $f(i)$ 表示将 $[1,i]$ 分为若干段的最优结果，有转移方程：

$$
\begin{cases}
f(0)=0\\
f(i)=\min_{1\le j\le i}\{f(j-1)+C(j,i)\}&i>0
\end{cases}
$$

我们定义 $f(i)$ 的最优转移点为 $opt(i)$。

结论1： 若 $C(l,r)$ 四边形友好，则 $opt(i)$ 随 $i$ 的增长单调不降。

证明： 反证法。

假设我们有 $i>j,opt(i)<opt(j)$，代入 dp 方程：

$$
\begin{equation}
f(opt(i)-1)+C(opt(i),i){\color{skyblue}\ =f(i)}\preceq f(opt(j)-1)+C(opt(j),i)
\end{equation}
$$

（因为 $opt(j)$ 不是 $f(i)$ 的最优转移点，所以代入的结果会更劣）

$opt(i)<opt(j)<j<i$，由四边形不等式有：

$$
\begin{equation}
C(opt(i),j)+C(opt(j),i)\preceq C(opt(i),i)+C(opt(j),j)
\end{equation}
$$

$(1)+(2)$ 并整理易得：

$$
f(opt(i)-1)+C(opt(i),j)\preceq f(opt(j)-1)+C(opt(j),j){\color{skyblue}\ =f(j)}
$$

所以 $opt(j)$ 不是 $f(j)$ 的最优转移点，矛盾。$\blacksquare$

$$
\boxed{
\begin{array}{c}
\text{无限制的序列分割问题中的决策单调性}\\
opt(i+1)\ge opt(i)
\end{array}
}
$$

我们上面的证明过程能给我们带来很多价值，因为转移方程中的 $f(j-1)$ 完全可以被替换成别的什么东西，或者干脆把它删去，定义 $opt(r)$ 为使 $C(l,r)$ 最优的 $l$，于是我们可以认为这是 $C(l,r)$ 一个独立的性质，这个结论将在后面问题的证明中发挥作用。

实际运用中的技巧

分治

分治法适用于任何我们不关心转移顺序的情况，非常灵活且强大。后面我们还会提到这一做法。

例题：LG3515 [POI2011]Lightning Conductor

本题中需要我们求的是这样一个式子：

$$
p_i=\left\lceil\max_{1\le j\le n}\left\{a_j+\sqrt{i-j}\right\}\right\rceil-a_i
$$

这里 $\prec$ 定义为 $>$，容易证明 $C(l,r)=\sqrt{r-l}$ 是四边形友好的，那么运用上面的结论，我们知道 $p_i$ 具有决策单调性。

另外注意到，$p_i$ 是独立的，i.e. $p_i$ 的取值不依赖于其他 $p_j\ (j\neq i)$，于是我们可以进行分治。

对于当前分治区间 $[l,r]$ 和候选决策点区间 $[tl,tr]$，暴力的计算 $p_{mid}$ 并记录其决策点 $s$，递归的处理 $[l,mid-1]\ (opt:[tl,s])$ 和 $[mid+1,r]\ (opt:[s,tr])$，每一层处理区间长度的总和是 $O(n)$ 的，层数为 $O(\log n)$，故总复杂度为 $O(n\log n)$。

注意尽管 $p_i$ 表达式中 $\max$ 是上取整，但是并不能在分治的计算过程中就取整，这样不影响答案的计算，但是会影响最优决策点的选择。

二分队列

在 dp 有单调递增的决策单调性时，容易发现每个点都是一个区间的最优转移点，此时我们可以使用单调队列维护 $(p,l,r)$ 表示 $p$ 可以作为最优转移点的区间。

每次转移要经过这样几个流程：

• 从队首取出转移点，如果 $r<now$，则删去队首重新取，否则使队首的 $l=now+1$。
• 使用取出的转移点计算 $f(now)$。
• 取出队尾，如果 $now$ 转移 $l$ 比用 $p$ 转移 $l$ 更优，则说明 $now$ 可以完全取代 $l$，此时删去队尾。否则，说明 $now$ 可以部分取代 $l$，那么在 $[l,n]$ 上进行二分，找出 $l$ 与 $now$ 的最优转移区间，插入单调队列即可。

复杂度为 $O(n\log n)$。

不要把二分队列和二分栈混为一谈，只要你发现你看的题解里面声称使用二分栈，实际上却有从栈底掏出元素的操作，这玩意就是二分队列。

• 例题：LG1912 [NOI2009] 诗人小G
• 巧妙 wqs：LG6246 [IOI2000] 邮局 加强版

我感觉 Aliens 这样做也是对的，但题解清一色斜优。等我有时间实践一下。

二分栈

事实上，二分栈的适用范围和我们上面描述的内容不太一致。常见的决策单调性决策点都是单调递增的，而在二分栈能解决的问题中，决策点整体呈现递减的趋势。

具体来说，如果在一个问题中我们证明了代价函数符合反向的决策单调性，也即包含优于交叉，不难发现，若 $f_i$ 的最优转移点是 $s_i$，则后续 dp 的最优转移点不可能出现在 $(s_i,i)$ 这一开区间内。形象地说，一个最优转移点的出现可以 inactivate 所有此时比自己大的候选转移点，所以我们说，决策点整体会呈现递减的趋势。

在这里需要注意，由于不断有新的候选转移点加入，如果我们列出决策点序列，其并不是单调递减的。

使用栈可以方便的理解上面这一过程，一个候选转移点是最优的当且仅当其在栈顶，很显然，若一个候选转移点成为栈顶，所有在其上方的转移点都会被弹出，但我们会向栈中推入新的转移点，所以决策点序列并非单调递减，每个决策点成为最优的时段也不是连续的一个区间。

我们已经看到了此问题和栈的相似性，类似二分队列，我们也可以用二分栈来维护所有决策点。取出栈顶进行转移，推入决策点时整体优则弹出栈顶，部分优则二分分界点即可。

这种决策单调性不易打表观察出来，所以实战中要多关注。

• 例题：LG5504 [JSOI2011] 柠檬
• 进阶：LG5244 [USACO19FEB] Mowing Mischief P（题解）

限制段数的序列分割问题

将序列分为恰好 $k$ 段，用 $f(i,k)$ 表示将 $[1,i]$ 分为 $k$ 段的最优结果，有转移方程：

$$
\begin{cases}
f(0,0)=0\\
f(i,0)=f(0,k)=\infty&i,k>0\\
f(i,k)=\min_{1\le j\le i}\{f(j-1,k-1)+C(j,i)\}&i,k>0
\end{cases}
$$

我们设 $g_k(l,r)=f(l-1,k-1)+C(l,r)$，即 $f(r,k)$ 从 $l$ 转移的结果，换言之，将 $[1,r]$ 分为 $k$ 段，并强制选择 $[l,r]$ 时的最优结果。

同时设 $opt_k(r)$ 表示 $f(r,k)$ 的最优转移点，或使 $g_k(l,r)$ 最优的 $l$。

结论2： 若 $C(l,r)$ 四边形友好，则 $g_k(l,r)$ 也四边形友好。

证明： 设 $a\le b\le c\le d$，由 $C(l,r)$ 四边形友好有：

$$
C(a,c)+C(b,d)\prec C(a,d)+C(b,c)\\
$$

两边同时加上 $f(a-1,k-1)+f(b-1,k-1)$，整理可得：

$$
g_k(a,c)+g_k(b,d)\prec g_k(a, d)+g_k(b,c)
$$

$\blacksquare$

结合结论1，我们不难得到 $opt_k(r)\le opt_k(r+1)$。

结论3： 若 $C(l,r)$ 四边形友好，则 $opt_k(r)\le opt_{k+1}(r)$。

证明： 反证法。

$k=1$ 时结论显然成立，所以下面考虑的都是 $k>1$ 的情况。

假设 $opt_k(r)>opt_{k+1}(r)$，也就是说，如果我们将 $f(r,k)$ 所对应的序列分割方案表示为 $part_1:[a_k,d_k],\dots,[a_1,d_1]$，$f(r,k+1)$ 对应的方案表示为 $part_2:[b_{k+1},c_{k+1}],\dots,[b_1,c_1]$，那么有 $a_1>b_1$。

容易发现的是，由于 $part2$ 比 $part1$ 多一段，必然存在一个 $[b_t,c_t]\subset[a_t,d_t]$。

于是，我们有了 $a_t\le b_t\le c_t\le d_t$，如下图，构造 $part_3$ 与 $part_4$，其中 $part2$ 和 $part3$ 的省略部分相同，$part1$ 和 $part4$ 的省略部分相同。

由于 $part1$ 和 $part2$ 分别是 $f(r,k)$ 和 $f(r,k+1)$ 的最优划分，所以：

$$
\begin{equation}
\begin{cases}
part_2\prec part_3\\
part_1\prec part_4
\end{cases}
\Rightarrow
part_1+part_2\prec part_3+part_4
\end{equation}
$$

考虑蓝色和黄色的四个区间，根据 $C(l,r)$ 的四边形友好性，有：

$$
C(a_t,c_t)+C(b_t,d_t)\prec C(a_t,d_t)+C(b_t,c_t)
$$

也就容易推出：

$$
\begin{equation}
part_3+part_4\prec part_1+part_2
\end{equation}
$$

显然，$(3)(4)$ 矛盾。$\blacksquare$

综合结论2和结论3，我们可以得到在限制段数的序列分割问题中的决策单调性：

$$
\boxed{
\begin{array}{c}
\text{限制段数的序列分割中的决策单调性}\\
opt_{k-1}(r)\le opt_k(r)\le opt_k(r+1)
\end{array}
}
$$

实际运用中的技巧

直接运用决策单调性

原 dp 方程是 2D/1D 的，我们可以直接在二维上运用决策单调性，当然需要注意的是，由于 $opt_k(r)$ 需要使用 $opt_k(r+1)$，所以转移顺序需要发生改变。

下面来证明这样做的复杂度，假设 $n,k$ 同阶。

$$
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^k(opt_j(i+1)-opt_{j-1}(i)+1)\\
=&O\left(\sum_{i=2}^{n+1}\sum_{j=1}^kopt_j(i)-\sum_{i=1}^n\sum_{j=0}^{k-1}opt_{j}(i)\right)\\
=&O\left(\sum_{j=1}^k(opt_j(n+1)-opt_j(1))+\sum_{i=1}^n(opt_k(i)-opt_0(i))\right)\\
=&O(n^2)
\end{aligned}
$$

所以直接运用决策单调性进行优化的复杂度是 $O(n^2)$。

例题：

• LG4072 [SDOI2016] 征途
• CF321E Ciel and Gondolas
• LG4767 [IOI2000] 邮局

分治

你也可以对于每一层（以分割段数为关键字）分别进行分治，这样做的总复杂度是 $O(nk\log n)$，这个 $\log$ 给我们带来的好处是，我们可以方便的使用类似于莫队的维护方法，来计算复杂的代价函数，比如说区间颜色数（CF833B），区间逆序对数（LG5574），区间小 Z 的袜子（CF868F）等等。

具体的，维护 $l,r$ 指针，分治过程中每次查询就暴力跳，每个区间跳指针的次数是 $O(len)$ 的，故指针的总移动次数就是 $O(n\log n)$ 级别的。

区间 dp

每次将序列中两个元素合并（或者是每次将一个元素分裂），最小化使序列中只剩一个元素的代价。设 $f(l,r)$ 表示将 $[l,r]$ 合并为一个元素的最小代，有转移方程：

$$
\begin{cases}
f(l,l)=C(l,l)\\
f(l,r)=\min_{l\le i<r}\{f(l,i)+f(i+1,r)+C(l,r)\}
\end{cases}
$$

结论4： 若 $C(l,r)$ 是四边形友好的，注意这里需要区间包含单调性，则 $f(l,r)$ 满足四边形不等式。

证明： 假设 $a\le b\le c\le d$，对 $d-a$ 进行归纳。

$d-a=0$ 时，$a=b=c=d$，结论显然成立。

现在，假设我们有 $a\le d'<d$，由归纳假设，对于较小的 $d-a$，结论均成立。

首先，以 $d'$ 为转移点写出 $f(a,d)$：

$$
f(a,d)=f(a,d')+f(d'+1,d)+C(a,d)
$$

下面进行分类讨论。

• 若 $d'\in[a,b)\cup[c,d)$，我们不妨设 $d'\in[c,d)$，另一半是完全一样的分析方法。

  $$
  \begin{aligned}
  f(a,d)+f(b,c)&={\color{skyblue}f(a,d')}+f(d'+1,d)+C(a,d)+{\color{skyblue}f(b,c)}\\
  &\succeq {\color{yellow}C(a,d)}+{\color{skyblue}f(a,c)+f(b,d')}+f(d'+1,d)\\
  &\succeq {\color{yellow}C(b,d)}+f(a,c)+f(b,d')+f(d'+1,d)\\
  &\succeq f(b,d)+f(a,c) \ \blacksquare
  \end{aligned}
  $$

• 若 $d'\in[b,c)$，我们取 $c'\in[b,c)$，不妨设 $c'\le d'$，另一种情况是完全一样的分析方法。

  首先以 $c'$ 为转移点写出 $f(b,c)$：

  $$
  f(b,c)=f(b,c')+f(c',c)+C(b,c)
  $$

  接下来直接推式子：

  $$
  \begin{aligned}
  &f(a,d)+f(b,c)\\
  =\ &f(a,d')+f(d'+1,d)+{\color{skyblue}C(a,d)}+f(b,c')+f(c'+1,c)+{\color{skyblue}C(b,c)}\\
  \succeq\ &{\color{skyblue}C(a,c)+C(b,d)}+{\color{yellow}f(a,d')}+f(d'+1,d)+{\color{yellow}f(b,c')}+f(c'+1,c)\\
  \succeq\ &C(a,c)+C(b,d)+{\color{yellow}f(a,c')+f(b,d')}+f(d'+1,d)+f(c'+1,c)\\
  \succeq\ &f(a,c)+f(b,d)\ \blacksquare
  \end{aligned}
  $$

综上，运用归纳法，结论成立。$\blacksquare$

在证明了 $f(l,r)$ 满足四边形不等式后，运用结论1的分析方式，设 $opt(l,r)$ 为 $f(l,r)$ 的最优转移点，我们容易得到：

$$
\boxed{
\begin{array}{c}
\text{区间 dp 中的决策单调性}\\
opt(l,r-1)\le opt(l,r)\le opt(l+1,r)
\end{array}
}
$$

于是，我们也可以直接运用决策单调性来优化区间 dp，与上一部分中一样的分析方式，我们可以得到优化后的复杂度为 $O(n^2)$。

例题：LG1880 [NOI1995] 石子合并 加强至 $n\le 5000$

---

Reference

• Quadrangle Inequality Properties by uoibir
• DP的决策单调性优化总结 by command_block

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。