斜率优化是将一类 \(O(n^2)\) 的 DP 状态转移优化至 \(O(n \log n)\) 甚至 \(O(n)\) 的方法。
用一个 atcoder dp contest 的最后一题来讲解：
dp_z Frog-3
https://atcoder.jp/contests/dp/tasks/dp_z
题意：有 \(n\) 个石头，一只青蛙初始站在第 \(1\) 块上。它可以执行若干次以下操作：
- 跳到第 \(j(i < j \le n)\) 块石头上，并花费 \((h_i - h_j) ^ 2 + c\) 的代价。
求青蛙到达第 \(n\) 块石头的最小代价。
\(2 \le n \le 2 \times 10^5, 1 \le c \le 10^{12}, \mathbf{1 \le h_1 < h_2<...<h_n\le 10^6}\)
分析：
令 \(dp_i\) 表示走到第 \(i\) 块石头的最小代价。
不难写出状态转移方程：
\[dp_i = \min_{j < i} \{dp_j + (h_j - h_i)^2 + c\} \]也就是找到在这个式子 \(dp_i = dp_j + (h_j - h_i)^2 + c\) 中使得 \(i\) 最小的 \(j\)。
为了使用斜率优化，我们需要将其转化为 \(y = kx + b\) 的形式，其中 \(x\) 和 \(y\) 是只和 \(j\) 有关的式子，\(k\) 是只和 \(i\) 有关（已知）的式子。而 \(b\) 和 \(dp_i\)（未知）有关，需要最小化。也就是说，在平面上分布有若干个点 \((x_j, y_j)\)，需要找到一个点，使得经过这个点的直线与 \(y\) 轴的交点最小。（截距最小）
即：
\[\color{red}{dp_j + h_j^2} = \color{blue}{2h_j}\color{green}{h_i}+\color{purple}{dp_i - h_i - c} \]\[\color{red}y = \color{blue}k \color{green}x + \color{purple}b \]例如这个题目假设 \(h_1 = 1,h_2 = 2\)，我们求出了 \(dp_1 = 0, dp_2 = 7\)，那么平面上分布有两个点 \((x_1,y_1)=(1,1)\) 和 \((x_2,y_2)=(2,11)\)：
现在要求出 \(dp_3\)，并且 \(h_3 = 3\)。以 \(2h_3=6\) 为斜率，画出两条线，分别是 \(j=1\) 和 \(j=2\) 时候对应的线：
可以发现是 \(j=1\) 的时候斜率更小，因此更优的决策点应该是 \(j=1\)。
【未完待续】
标签：le,color,最小,斜率,优化,dp From： https://www.cnblogs.com/Zeardoe/p/16749316.html