随机做题过程中遇到感觉还不错的题就会记录下来，随缘更新
CF360B Levko and Array
考虑二分答案 \(x\) 后用 dp 检验
设 \(dp_i\) 为钦定 \(a_i\) 不会改变后，在 \(i\) 之前有多少数字可以不改变位置，有转移方程
\[dp_i = \max\limits_{j < i \;\and\;|a_i - a_j| \leq (i - j)\times x}\{dp_j + 1\}
\]
若有 \(dp_i + k \ge n\) 则成立
gym104466C Cosmic Commute
首先 BFS 计算出任意一点 \(i\) 到终点的距离 \(ed_i\) 和到起点的距离 \(st_i\) ，考虑不用传送，显然最终答案为 \(st_n\)
考虑可以传送的特殊点 \(u\)，其到达终点的期望距离应当为 \(\frac{1}{k - 1} \times \sum\limits_{v \in S, v \ne u}(st_u + ed_v)\) ，我们将其记作 \(dis_u\)
易得最终答案为 \(\min\limits_{u \in S}(st_n, dis_u)\)