跳转至

4.3.1 决策单调性相关

SMAWK, Wilber, Eppstein 和其他的神秘东西大概是不会补的。

下面讲的都是最小化，要最大化就把不等号反向一下。

约定一下，\(\operatorname{argmin}f(x)\) 指的是使 \(f(x)\) 取到最小值的 \(x\)，\(\operatorname{argmax}f(x)\) 同理。

决策单调性

顾名思义，其实就是对于一个转移方程

\[ f_i=\min_{j<i}f_j+w(j,i) \]

我们有 \(\operatorname{argmin}f(i)\) 关于 \(i\) 单调不降。

四边形不等式

考虑一个二元函数 \(w(l,r)\)，如果这个函数满足对于任意的 \(p_1\le p_2\le p_3\le p_4\) 均有

\[ w(p_1,p_3)+w(p_2, p_4)\le w(p_1,p_4)+w(p_2,p_3) \]

也就是交叉优于包含，我们就称它是满足四边形不等式的。

在证明的时候我们通常使用它的另一个形式

\[ w(l-1,r)+w(l,r+1)\le w(l, r)+w(l-1,r+1) \]

端点只移动了 \(1\)，贡献更好算一点。

如果代价函数满足四边形不等式，那么它就一定满足决策单调性。

感性理解一下，把上面的式子换成

\[ w(l,r)-w(l-1,r)\ge w(l,r+1)-w(l-1,r+1) \]

我们把右边称为决策位置，左边称为决策点。考虑决策位置的变动。

此时，决策点靠右的，向最值侧的增长速度不慢于靠左的。

所以靠左的一旦被靠右的击败，那既然增长速度慢于靠右的，那就不会再胜过靠右的，从而有决策点单调。

事实上根据 LCA 的 PPT，条件的强度应该是这样从弱到强排的：

  1. 决策单调性：决策点关于决策位置单调
  2. 半完全单调性：对于任意决策点 \(x,y\)，总存在一个决策位置 \(p\)（可以是正负无穷），使得 \(p\) 的一侧的决策位置，用 \(x\) 更优，另一侧的决策位置，用 \(y\) 更优。
  3. 完全单调性：只考虑任意两个决策和任意两个位置，最优决策点都关于决策位置是单调的。
  4. 四边形不等式
  5. 双线性：\(w(i,j)=A_iB_j+C_i+D_j\)，其中这四个都是固定的（斜率优化）。

其中每个都包含上一个。

分治 / 整体二分

你说得对，但上面的东西有什么用？

从简单的情况开始，假设我们要解决一个离线的问题。也就是 \(w(i,j)\) 的计算和 \(f(i)\) 没有关系。也就是

\[ f(i)=\min_{j=1}^{i}g(j)+w(i,j) \]

其中 \(g\) 给定。

所以咋做来着

因为有决策单调性，所以我们对决策位置 \(i\) 找到它的最优决策点 \(j\)，那么 \([1,i)\) 的最优决策点所在的范围是 \([1,j]\)，\((i,n]\) 的最优决策点所在的范围是 \([j,n]\)。利用这个性质，可以整体二分。

例题一 / LOJ#2035. [SDOI2016] 征途

简要题意是把序列划分成 \(m\) 段，每段和的方差最小。

先要刻画这个 \(v\times m^2\)，我们知道方差的定义式是

\[ v=\sum_{i=1}^{m}\frac{(x_i-\overline{x})^2}{k} \]

这里的 \(\overline{x}=\frac{\sum_{i=1}^{m}x_i}{m}\)。

简单推一下式子

\[ \begin{aligned} \sum_{i=1}^{m}\frac{(x_i-\overline{x})^2}{m}&=\sum_{i=1}^{m}\qty(\frac{x_i^2-2x_i\cdot \overline{x}+\overline{x}^2}{m}) \end{aligned} \]

记 \(X=\sum_{i=1}^{m}x_i\)，那么就有

\[ \begin{aligned} v\times m^2=\qty(\sum_{i=1}^{m}mx_i^2)-2X^2+X^2=-X^2+m\sum_{i=1}^{m}x_i^2 \end{aligned} \]

二分队列

通常大多数决策单调性还满足半完全单调性。也就是对任意决策点 \(i<j\)，肯定有一个决策位置 \(k\) 使得 \(k\) 一侧的决策位置，用 \(i\) 更优，另一侧的决策位置，用 \(j\) 更优。

也就是每个点 \(p\) 对应的最优决策位置是一段区间。

一个大致的想法是，开一个单调队列状物，当前队首最优，某个时刻过后下一个更优，再接下来再下一个更优……

举个例子。

P1912 [NOI2009] 诗人小G

设 \(S_i=i+\sum_{j=1}^{i}\operatorname{len}(j)\)，我们直接快进到 DP 式子

\[ f_{i}=\min_{j=0}^{i-1}\{f_j+\abs{s_i-s_j-1-L}^{P}\} \]

这东西有决策单调性。

考虑维护一个队列，对队列每对相邻的位置 \(i,i+1\) 求出一个 \(k\)，表示当决策位置 \(\ge k\) 的时候 \(i+1\) 要优于 \(i\)。

插入时，设 \(q\) 为末尾 \(-1\)，\(p\) 为末尾，\(i\) 为要插入的数。如果 \(i\) 超过 \(p\) 的位置比 \(p\) 超过 \(q\) 的位置还要小，那么 \(p\) 显然就没有用了，因为你可以直接用 \(i\) 代替它。

整个转移如代码所示

for (int i = 1; i <= n; i++) {
    while (hh < tt && divide[hh] <= i)  hh++;
    f[i] = w(i, q[hh]);
    from[i] = q[hh];
    // divide[tt - 1] 前 q[tt - 1] 优，后 q[tt] 严格优
    // bound(q[tt], i) 前 q[tt] 优，后 i 严格优
    while (hh < tt && divide[tt - 1] >= bound(q[tt], i))
        tt--;
    divide[tt] = bound(q[tt], i);
    q[++tt] = i;
}

bound(i, j) 是求 \(i,j\) 的分界点 \(k\)，在 \(k\) 之后 \(j\) 被 \(i\) 超过。通过二分，可以简单求出这个 \(k\)，实现如下。

// 第一个 y 比 x 优的决策位置
inline int bound(int x, int y) {
    int l = x, r = n + 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (w(mid, x) < w(mid, y))
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}

P3515 [POI2011] Lightning Conductor

正反各做一遍。这样就可以把绝对值消掉了。

值得一提的时候，在二分的时候，若 \(w(i, j)\) 直接用取整后的结果可能会导致找到错误的函数交点。一个可能的解释是，在函数值大时，由于开根增长的速度不快，所以很多 \(a_j+\sqrt{i-j}\) 是一段很长的平台，如果直接利用取整，会导致这些函数在平台段的值全部相同，求不出正确的最大值。

Code Link

二分栈

通常来讲还有一个叫“二分栈”的东西，但是其实真正是二分栈的题目很稀有，大部分时候声称是二分栈的其实是二分队列，因为最优决策还是在取栈底。

大部分时候见到这种都是满足反四边形不等式，就是包含优于交叉。

P5504 [JSOI2011] 柠檬