Skip to main content

DP 优化

Summary

DP 优化收录三种把动态规划复杂度降下来的手段。斜率优化针对形如 fi=min(fj+w(i,j)) 且整理后含斜率一次函数的转移，把决策看作平面上的点，最优转移等价于在下凸壳上找与给定斜率相切的点，斜率与横坐标都单调时用单调队列均摊 O(1) 维护。四边形不等式利用代价函数的决策单调性，把区间 DP 从 O(n^3) 优化到 O(n^2)。WQS 二分（带权二分、凸优化）处理恰好选 k 个且最优值关于 k 为凸的问题，给该类元素附加惩罚再二分惩罚值，把数量限制转化为普通求解。

参考资料​

斜率优化​

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

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

四边形不等式优化​

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

WQS 二分​

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

例题​

洛谷 P3195 [HNOI2008] 玩具装箱

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

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

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

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

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