决策单调性——学习笔记

对于形似 \(f(i) \leftarrow f(j)+w(j,i)\)\(DP\) ,我们定义 \(pos_i\) 表示 \(i\) 的决策点位置。

所谓决策单调,即 \(pos\) 是单调的。分增和减两种。比如,若 \(i<j\)\(pos_i \le pos_j\)

我一直想错的一个地方,就是 \(pos\) 是可能不连续的。

对于一个决策点,它控制一段区间,但有些点可能太垃圾,不是任何点的最优解。

决策单调这个性质的关键在于,对应任意 \((i,j)\) ,存在一分界点 \(p\)\(p\) 的两边分别是一方更优。

如何判断决策是否单调,一般是试图证明:

对于 \(k<p<j<i\) ,若对于 \(j\) , \(p\)\(k\) 更优,则对于 \(i\) ,也有 \(p\)\(k\) 优。

可以感性理解,打表验证,或者推推式子直接证出来。所谓四边形不等式,就是把上面这条件化一下。

决策单调性 \(DP\) 一般有 \(3\) 类转移方法:

  • 分治。就是每次暴力算 \(pos_{mid}\) ,然后分两半递归。

    这样两种方向都可以做,但有个很大的局限是只能处理 \(f(i) \leftarrow g(j)+w(j,i)\) 这样 \(g\) 已知的。

  • \(pos\) 增,可以维护单调队列。

    当前处理到了 \(i\) , 则 \((i,n]\) 的决策点被分成若干段,用单调队列存。

    每次转移 \(i\) 就直接由队头得到,然后需要更新区间。

    \(i\) 的控制区间一定是 \((x,n]\) 或没有,队尾 \(pop\) 一下,然后二分算左端点即可更新。

  • \(pos\) 减,维护单调栈。

    栈中的元素是决策点,而且其控制区间是单调的。

    \(push\) \(i\) 前,若 \(top\)\(top-1\) 的分界点小于 \(i\)\(top\) 的分界点,说明 \(top\) 没卵用,不断 \(pop\) 即可。

    上面这样搞就能满足区间单调了。那转移就 \(pop\) 到当前最优的地方即可。

感性理解真舒服。