斜率优化 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 = f_j + {B_j} ^ 2$
   • $k = 2 \times A_i$
   • $x = B_j$
   • $b = f_i - {A_i} ^ 2$

5. 当 $x$ 单调递增时：

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

6. 已知两个点 $\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