DP 优化

参考资料

• 斜率优化 - OI Wiki
• 四边形不等式优化 - OI Wiki
• WQS 二分 - OI Wiki

斜率优化

当 DP 转移形如 $f_i=\min_j\set{f_j+w(i,j)}$，且把含 $j$ 的项整理后能写成「关于某个随 $i$ 单调的斜率的一次函数」时，可用 斜率优化。

把每个决策 $j$ 看作平面上一个点，最优转移等价于在这些点构成的 下凸壳 上找到与给定斜率相切的点。当斜率与横坐标都单调时用单调队列维护凸壳，均摊 $O(1)$ 转移，总复杂度降到 $O(n)$；否则可在凸壳上二分。

四边形不等式优化

若代价函数 $w$ 满足 四边形不等式：对 $a\le b\le c\le d$ 有 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$，则相应 DP 的最优决策点具有单调性。利用决策单调性，可把区间 DP 由 $O(n^3)$ 优化到 $O(n^2)$，把一类一维 DP 优化到 $O(n\log n)$。

WQS 二分

WQS 二分（带权二分 / 凸优化）用于「恰好选 $k$ 个某类元素」且最优值关于 $k$ 为凸的问题。给每个该类元素附加惩罚 $\lambda$ 并去掉「恰好 $k$ 个」的限制求最优，再二分 $\lambda$ 使最优解恰好用了 $k$ 个，从而把带数量限制的问题转化为一次普通求解。

例题

洛谷 P3195 [HNOI2008] 玩具装箱

$n$ 个玩具排成一列，第 $i$ 个长 $C_i$。将其划分为若干连续段，每段装入一个一维容器，相邻玩具间留 $1$ 单位间隔，则段 $[i,j]$ 的容器长为 $j-i+\sum_{k=i}^{j}C_k$，费用为该长度与 $L$ 之差的平方。求最小总费用。

洛谷 P4767 [IOI 2000] 邮局 加强版

数轴上有 $n$ 个村庄，要建 $m$ 个邮局，使每个村庄到最近邮局的距离之和最小，求该最小值。

洛谷 P2619 [国家集训队] Tree I

给定 $n$ 个点 $m$ 条边的无向图，每条边为黑或白且带权，求恰好包含 $k$ 条白边的生成树中边权和最小的一棵。