MENU

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

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)>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$ 具有决策单调性。

四边形友好的证明


设 $a\le b\le c\le d$,我们要证的即为:

$$
\sqrt{c-a}+\sqrt{d-b}>\sqrt{d-a}+\sqrt{c-b}
$$

移项:

$$
\sqrt{d-b}-\sqrt{c-b}>\sqrt{d-a}-\sqrt{c-a}
$$

设 $f(x)=\sqrt{x+(d-c)}-\sqrt{x}$,只需证

$$
f(c-b)>f(c-a)
$$

$(\sqrt{x})'$ 单调递减,故 $f(x)$ 单调递减,$c-b<c-a$,故上式显然成立。$\blacksquare$

另外注意到,$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)$。

不要把二分队列和二分栈混为一谈,真正的二分栈根本就没有决策单调性,这里不展开来讲,但是只要你发现你看的题解里面声称使用二分栈,实际上却有从栈底掏出元素的操作,这玩意就是二分队列。栈这种数据结构显然是只允许对栈顶进行操作的。

例题:P1912 [NOI2009] 诗人小G

限制段数的序列分割问题

将序列分为恰好 $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)+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$。

容易发现的是,必然存在一个 $[b_t,c_t]\subset[a_t,d_t]$。这里提供一个偏感性的证明,我们尝试着让每个 $[b_i,c_i]$ 都不被包含:$[b_1,c_1]$ 不被 $[a_1,c_1]$ 包含,所以 $[b_1,c_1]$ 必然会占用 $[a_2,d_2]$ 的空间,以此类推,直到 $[b_k,c_k]$ 一方面被 $[b_{k+1},c_{k+1}]$ 挤压,一方面被 $[b_{k-1},c_{k-1}]$ 挤压,所以只能够被 $[a_k,d_k]$ 包含,矛盾。我认为这样是比较有说服力的,理性证明也是模仿上述过程即可。

于是,我们有了 $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)$。

分治

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

具体的,维护 $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=1$ 时,$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)$。


Reference

Last Modified: April 6, 2022
Archives Tip
QR Code for this page
Tipping QR Code