这题的朴素 dp 是显然的。
令 \(dp_i\) 表示跳到第 \(i\) 个石头的最小花费，有转移方程：
\[dp_i=\min_{j=1}^{i-1}\{dp_j+(h_i-h_j)^2+C\} \]直接转移是 \(O(n^2)\) 的，考虑优化。
首先对于 \(\min\) 以内的式子化简，得：
\[dp_j+h_i^2+h_j^2-2h_ih_j+C \]将与 \(j\) 无关的项剔除，得：
\[dp_j+h_j^2-2h_ih_j \]令 \(f_i\) 表示 \(dp_i+h_i^2\)，\(k\) 表示 \(-2h_i\)，得：
\[f_j+kh_j \]此时，我们考虑有两个转移点 \(j_1,j_2\)。
若 \(j_1<j_2\) 且 \(j_2\) 一定不比 \(j_1\) 更优，仅当：
\[f_{j_1}+kh_{j_1} \le f_{j_2}+kh_{j_2} \]移项，得：
\[kh_{j_1}-kh_{j_2} \le f_{j_2}-f_{j_1} \]两边同时除以 \(h_{j_1}-h_{j_2}\)（不等式要变号，因为 \(h_{j_1}-h_{j_2}<0\)）得：
\[k \ge \dfrac{f_{j_2}-f_{j_1}}{h_{j_1}-h_{j_2}} \]代入 \(k=-2h_i\)，得：
\[-2h_i \ge \dfrac{f_{j_2}-f_{j_1}}{h_{j_1}-h_{j_2}} \]两边同时乘以 \(-1\)，得：
\[2h_i \ge \dfrac{f_{j_1}-f_{j_2}}{h_{j_1}-h_{j_2}} \]然后我们发现这个式子与斜率的计算公式十分相似，于是考虑斜率优化。
具体地，我们分析三个候补转移节点 \(p_1,p_2,p_3\)，它们满足 \(p_1<p_2<p_3\)。
令 \(\operatorname{slope}(i,j)\) 表示 \(\dfrac{f_i-f_j}{h_i-h_j}\)。
若 \(p_2\) 是最优转移节点，则有：
\[2h_i \ge \operatorname{slope}(p_1,p_2) \]表示 \(p_1\) 一定不比 \(p_2\) 更优，并且有：
\[2h_i \le \operatorname{slope}(p_2,p_3) \]表示 \(p_3\) 一定不比 \(p_2\) 更优，也即，当：
\[\operatorname{slope}(p_1,p_2) \le \operatorname{slope}(p_2,p_3) \]时，有 \(p_2\) 为 \(p_1,p_2,p_3\) 中的最优转移节点。
这样每次选取最优转移节点，它们便组成了一个凸包。
由于题目保证 \(h_i\) 单调递增，
于是我们采用单调队列维护此凸包，
每次转移时从队头寻找最优转移节点，
转移完成后再从队尾弹出不是最优转移节点的节点即可。
这样转移的单次均摊时间复杂度降至 \(O(1)\)，总时间复杂度为 \(O(n)\)。
实现是简单的。
标签：slope,题解,kh,Frog,转移,2h,节点,dp From： https://www.cnblogs.com/XOF-0-0/p/18048907