决策单调性优化 DP

2D/1D DP 的决策单调性优化

2D/1D DP 指状态有两维、转移有一维的 DP。

定理：对于形如 $f(i,j)=\min\limits_{k=i}^{j-1}\{f(i,k)+f(k+1,j)\}+w(i,j)$ 的 DP 式，若：

区间包含单调性：对于 $i\le i'<j\le j'$ ，满足 $w(i',j)\le w(i,j')$ 。（（互相包含的两个区间）大区间大于小区间）

四边形不等式：对于 $i\le i'<j\le j'$ ，满足 $w(i,j)+w(i',j')\le w(i',j)+w(i,j')$ 。（包含大于交叉）

均满足，记 $f(i,j)$ 的决策点 $k=s(i,j)$ ，则 $s(i,j-1)\le s(i,j)\le s(i+1,j)$ 。（或写成 $s(i-1,j)\le s(i,j)\le s(i,j+1)$ ）（左边加一个点，决策点不动或左移）

可以证明，这样枚举决策，总时间复杂度为 $O(n^2)$ 。

四边形不等式的判定

若对于 $\forall i,j$ ，均有 $w(i,j)+w(i+1,j+1)\le w(i,j+1)+w(i+1,j)$ 成立，则 $w(i,j)$ 满足四边形不等式。
若 $w_1(i,j)$ 和 $w_2(i,j)$ 都满足四边形不等式（或区间包含单调性），则对于 $\forall c_1,c_2\ge0$ ， $c_1w_1+c_2w_2$ 也满足四边形不等式（或区间包含单调性）。
若存在前缀和 $f(i),g(i)$ 使得 $w(i,j)=f(j)-g(i)$ ，则 $w(i,j)$ 满足四边形不等式。若 $f(i),g(i)$ 单增，则 $w(i,j)$ 还满足区间包含单调性。
若 $h(x)$ 是递增的下凸函数，且 $w(i,j)$ 满足区间包含单调性和四边形不等式，则 $h(w(i,j))$ 也满足区间包含单调性和四边形不等式。
若『4.』中的 $h(x)$ 是不递增的下凸函数，则只能得出 $h(w(i,j))$ 满足四边形不等式。

1D/1D DP 的决策单调性优化

定理：对于形如 $f(i)=\min\limits_{j=1}^{i-1}\{f(j)+w(j+1,i)\}$ 的 DP 式，若 $w(i,j)$ 满足区间包含单调性和四边形不等式，则 $s(i)$ 满足单调性。

方法一. 分治

分治可以做有层次的 DP 形如 $f(d,i)=\min\limits_{j=1}^{i-1}\{f(d-1,j)+w(j+1,i)\}$ 。

对于区间 $[l,r]$ ，假设已经找到决策区间 $[s(l),s(r)]$ ，就可以暴力找出 $s(\text{mid})$ ，向左右递归 $[l,\text{mid}-1]$ 和 $[\text{mid}+1,r]$ 。

方法二. 二分 + 单调队列

维护每个决策点 $j$ 可以对哪些 $i$ 造成贡献，显然这些 $i$ 连成一个区间 $[l_j,r_j]$ 。维护每个 $j$ 的 $l_j$ ，有 $r_j=l_{j+1}-1$ 。于是使 $l_j$ 单增，查询时需要找到最大的 $<i$ 的 $l_j$ 。

现在考虑加入新决策点 $j$ ，将它和当前决策队列的队尾 $\text{last}$ 比较。二分找到最小的 $k$ 满足 $f(\text{last})<f(j)$ (?)，若 $k$ 在 $[l_{\text{last}},j]$ 区间上，则现在 $\text{last}$ 的贡献区间为 $[l_{\text{last}},k-1]$ ，而 $j$ 的贡献区间为 $[k,j]$ ；若 $k<l_{\text{last}}$ ，那么 $\text{last}$ 可被删除，再将 $j$ 与新的队尾比较。