动态规划——斜率优化DP

适用情况

适用于求解最优解（最大、最小）问题。

一般来说，原转移方程可以化为：［三部分——仅与 \(i\) 有关、仅与 \(j\) 有关、与 \(i\) 和 \(j\) 都有关且是单项式］的，都可以用斜率优化。

形式化的：原式可化为 \(dp_i = \min\limits_{j \in [l,r]}\{ \mathrm y_j - k_ix_j \} - a_i\)，
其中 \(y\)、\(k\)、\(x\) 均为人为规定与 \(dp\) 和常数有关的式子。

上凸壳与下凸壳

求解步骤

1. 对于任意状态转义方程，设 \(A_i\)，\(B_i\)，使状态转移方程转化为

   • \(f_i = \min(f_j + (A_i - B_j) ^ 2)\)

2. 当 \(i\) 从 \(j\) 转移来时，丢掉 \(\min\)

   • \(f_i = f_j + {A_i} ^ 2 + {B_j} ^ 2 - 2 \times A_i \times B_j\)

3. 将仅和 \(j\) 有关的放在左边，其他的放在右边

   • \(f_j + {B_j} ^ 2 = 2 \times A_i \times B_j + f_i - {A_i} ^ 2\)

4. 仅和 \(j\) 有关的，是已经求出来的，看做 \(y\)；仅和 \(i\) 有关的，再附加上常数，是需要求的，看做纵截距；剩下的与 \(i\) 和 \(j\) 都有关，将其中仅与 \(j\) 有关的因式看做 \(x\)，剩余的因式看做斜率

   • \(y_j = f_j + {B_j} ^ 2\)
   • \(k_i = 2 \times A_i\)
   • \(x_j = B_j\)
   • \(b = f_i - {A_i} ^ 2\)

5. 过点 \((x_j, y_j)\) 做一条斜率为 \(k_i\) 的直线；则 \(b = f_i - {A_i} ^ 2\) 为该直线的纵截距。

当 \(x\) 单调递增时：

- 若 $k$ 单调递增或递减，可以使用单调栈维护
- 若 $k$ 无单调性，可以在数组内二分斜率，找到与目标相切的点

已知两个点 \(\text{A}(x_1, y_1)\)，\(\text{B}(x_2, y_2)\)，则直线 \(\text{AB}\) 斜率为 \(\dfrac{y_1 - y_2}{x_1 - x_2}\)

• 小问题：当 \(x\) 非单调递增呢？我还没学QwQ

题单

可以参考这个：https://www.luogu.com.cn/training/5352

Reference

[1] https://www.cnblogs.com/littlehb/p/15936381.html

热门相关：我有一座恐怖屋   重生之将门毒后   宠物小精灵之庭树   重生成偏执霍少的小仙女   异能特工：军火皇后