DP 优化 - 决策单调性与四边形不等式优化

决策单调性与四边形不等式

决策单调性

解决形如 \(dp_i = \min_{j\in[1,i] w(j,i)}\) 的最优化问题时，令 \(\text{opt}_i\) 为 \(i\) 的最优决策点。

定义：

决策单调性指的是 \(\forall i_1, i_2, i_1 \lt i_2, \text{opt}_{i_1} \le \text{opt}_{i_2}\)。

证明：

考虑两个决策 \(j_1,j_2\) 在 \(i\) 增长的时候变化。

证明在 \(i \leftarrow i + 1\) 时决策点 \(j_2\) 的权值比决策点 \(j_1\) 的权值往最优的方向增长的更快，则决策点递增。

如在 \(\min\) 的最优化问题时：

\(\Delta w(j_1,i) \gt \Delta w(j_2,i) \Leftrightarrow\) 最优决策点单调递增

\(\Delta w(j_1,i) \lt \Delta w(j_2,i) \Leftrightarrow\) 最优决策点单调递减

\(\max\) 问题同理。

四边形不等式

四边形不等式指的是对于二元函数 \(w\)，和 \(\forall a \le b \le c \le d\)，满足：

\[w(a,d)+w(b,c) \ge w(a,c) + w(b,d) \]

俗称相交小于包含。

这个东西一般用作决策单调性的证明。

优化 dp

分治

void solve(int l, int r, int opt_l, int opt_r) 表示分治到区间 \([l,r]\)，决策点是 \([\text{opt}_l, \text{opt}_r]\)。

每次分治里面找到 \([l,r]\) 的中点 \(mid\)，求出 \(mid\) 的最优决策点 \(\text{opt}_{mid}\) 并记录。

最后递归分治处理：

solve(l, mid - 1, opt_l, opt_mid); 和 solve(mid + 1, r, opt_mid, opt_r);

该算法的局限性在于只能在两个不同的数组（决策点和被转移的）中进行，不能将一个数组转移到自己。
即必须知道决策点的 dp 值才可以转移。

二分队列

不要看 OI wiki！不要看 OI wiki！不要看 OI wiki！