题目链接


一、思路解析

首先来看题目的询问内容。题目要求小$R$至少获得$k$分的前提下花费的最小金币数。显然这是一个二分答案,因为当金币花少了以后,由于灵活性问题,分数达不到$k$,并且较大的花费带来的变化严格包含了较小花费带来的变化(即只会使结果变得更优,而不是更劣)。结果随着答案的变化呈现出不严格的单调性,所以考虑二分答案。
二分答案之后的验证就是一个典型的线性动态规划。设状态$dp_i$表示跳到格子$i$所能得到的最大得分。不难发现状态转移方程如下:
$$dp_i \; = \; \max\limits_{\max(1,d-v) \leq \; x_i - x_j \; \leq d + v} {dp_j}\;+\;s_i$$
可以用两层循环计算状态,但是时间复杂度为$O(n^2)$(算上二分过程则为$O(n^2 \log n)$),对于本题的数据范围($n \leq 5 \times 10^5$)而言太大了。