AT_dp_z Frog 3 题解
KidA
·
·
题解
这题的朴素 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)。
实现是简单的。