形式1(区间 dp)
\[dp_{l,r}=\min_{l \le k < r}\{dp_{l,k}+dp_{k+1,r}\}+w(l,r) \]若 \(w(l,r)\) 满足:
- 区间包含单调性:\(\forall l_1 \le l_2 \le r_2 \le r_1\),\(w(l_2,r_2) \le w(l_1,r_1)\)
- 四边形不等式: \(\forall 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)\)
则 \(dp_{l,r}\) 满足四边形不等式,其决策点 \(op_{l,r}\) 满足:
\[op_{l,r-1} \le op_{l,r} \le op_{l+1,r} \]复杂度降至 \(\mathcal O(n^2)\)
eg. 合并石子
形式2
\[dp_{r}=\min_{1 \le l < r}w(l,r) \]若 \(w(l,r)\) 满足四边形不等式,则决策具有单调性。
对决策区间分治,具体来说,每次求出中点的决策点,然后分割给左右区间即可。
复杂度 \(\mathcal O(n \log n)\)
eg. Lightning Conductor
形式3
\[dp_{r}=\min_{1 \le 1 < r} \{dp_l+w(l,r)\} \]若 \(w(l,r)\) 满足四边形不等式,则决策具有单调性。
但无法提前计算中点的决策点,不能直接分治,此时使用二分栈。
因为决策具有单调性,以任意一点为决策点的点构成一段连续的区间。
那么维护一个栈,每次用新的决策点和栈顶比较,弹出较劣的栈顶。
最后栈顶一定存在一部分区间比当前决策点有,二分找出此区间即可。
eg. 有决策单调性的题目 玩具装箱,诗人小G
形式4
\[dp_{i,j}=\min_{k < j}\{dp_{i-1,k}+w(k,j)\} \]1.
若 \(dp_i\) 满足凸性,使用 wqs 二分得到:
\[dp_{i}=\min_{j < i}\{dp_j+w(k,j)+v\} \]转化为形式 \(3\)
eg. 邮局加强版
2.
1.直接使用四边形不等式优化
复杂度 \(\mathcal O(n^2)\)
2.逐层计算 \(dp_i\) , 转化为形式 \(2\)
复杂度 \(\mathcal O(n^2 \log n)\)
eg. 邮局