四边形不等式 学习笔记
定义
四边形不等式(QI)如果对于函数 \(w(l, r)\),\(l_1\le l_2\le r_1\le r_2, w(l_1, r_1) +w(l_2, r_2)\le w(l_1, r_2) + w(l_2, r_1)\),则称 \(w\) 满足四边形不等式,函数 \(w\) 的二维矩阵被称作蒙日矩阵。
一般只能用于求 \(\min\) 的DP。
石子合并模型
对于 DP 方程:
\[f_{l, r} = \min_{k\in[l, r - 1]}(f_{l, k} +f_{k + 1, r}) + w(l, r) \]如果 \(w\) 满足 QI 与 包含单调性(\([l, r]\subseteq[ll, rr], w(l, r)\le w(ll, rr)\)),则 \(f\) 满足 QI,且 \(f\) 具有决策单调性,具体而言,设 \(m(l, r) = \text{arcmin}_{k} (f_{l, k} +f_{k +1, r})\),则有 \(m(l,r-1)\le m(l, r)\le m(l+1, r)\),证明可以反证+放缩法。
利用决策单调性可以把这个 DP 在 \(O(n^2)\) 的时间复杂度内计算出来,具体而言记录每个状态的最优决策点,转移上下界只需要枚举到上不等式即可,这样对于每一层 \(m(l, r - 1)\le m(l,r)\le m(l + 1, r)\le m(l + 1, r + 1)\le m(l+2,r+1)\),所以对于相同长度的状态,他们这一层总共的枚举量是 \(O(n)\) 的。
分 \(k\) 组模型
对于 DP 方程:
\[f_{i, j} = \min_{k <i} f_{k, j - 1} +w(k, i) \]如果 \(w\) 满足 QI 和包含单调性,则 \(f\) 具有决策单调性,\(m(l,r-1)\le m(l, r)\le m(l+1, r)\)。
运用决策单调性,可以用分治法在 \(O(nk\log n)\) 的时间内解决这个问题。
使用同石子合并的技巧,可以在 \(O(n^2)\) 的时间内解决这个问题。
1D-1D模型
对于 DP 方程:
\[f_{i} = \min_{j <i} f_{j} +w(j, i) \]如果 \(w\) 满足QI,则对于 \(a\le b, m(b)\ge m(a)\),证明依旧运用 QI + 放缩。
运用决策单调性,使用二分栈在 \(O(n\log n)\) 的时间内解决这个问题,具体而言,对于每个决策点,考虑哪些状态以它为最优决策点,枚举决策点,维护每个状态当前的最优决策点,然后对于新来的决策点,以它为最优决策点的状态一定是一段后缀,二分出后缀开头即可。
存在 \(O(n)\) 的算法,名字是 SMAWK。
标签:le,不等式,决策,笔记,DP,QI,四边形,单调 From: https://www.cnblogs.com/MoyouSayuki/p/18391759