SP27341 AR2015PF - Jumping Joey

从前有只青蛙叫做 Joey，他的家旁边有一个长长的池塘，池塘上有许多荷叶。Joey 喜欢在荷叶上跳跃，因为他不喜欢弄湿自己。让我们帮助 Joey 穿过这个池塘。 为了简化问题，我们假设池塘是一段长度为 $L$ 的直线。上面有 $n$ 片荷叶，我们从左到右依次编号：最左边的荷叶编号为 1，第二片为 2，以此类推。一开始，Joey 位于池塘最左端。接着，他移动到第一片荷叶，然后去第二片，依次向右，最终从第 $n$ 片荷叶跳到池塘的右端。 Joey 可以通过跳跃或者游泳来移动。如果两个位置之间的距离不超过 $D$，他就可以通过跳跃到达。他可以随时游泳，但他不喜欢弄湿自己，所以我们需要尽量减少 Joey 游泳的次数。 然而，事情并不是那么简单。池塘的每两个相邻位置之间都有绳子连接，具体情况如下： - 左端与第一片荷叶之间； - 最后一片荷叶与右端之间； - 每两片相邻荷叶之间。 设： - $P_i$ 代表第 $i$ 片荷叶 ($1 \le i \le n$)，$P_0$ 为左端，$P_{n+1}$ 为右端。 - $r_i$ 是绳子 $R_i$ 的长度 ($0 \le i \le n$)。 - $p_i$ 是 $P_i$ 的位置 ($0 \le i \le n+1$)。显然 $p_0 = 0$，$p_{n+1} = L$ 并且 $p_i < p_{i+1}$ 且 $r_i \ge p_{i+1} - p_i$ ($0 \le i \le n$)。 当 Joey 在 $P_i$ 时，他可以拉动 $R_i$，这样 $P_{i+1}$ 就会向 Joey 移动。一旦绳子 $R_{i+1}$ 绷紧（即绳长等于绳子连接两荷叶间的实际距离），那么 $P_{i+2}$ 也会被带动（以此类推）。如果某根绳子没有绷紧，则不会影响后面的荷叶。此外，假如所有绳子都绷紧直到 $P_{n+1}$，荷叶也不会移动（因为 $P_{n+1}$ 是固定的，不可移动）。通过以下的例子来更好地理解这一机制。 **示例 1：** 假设 Joey 位于 $P_2$，并且 $p_2 = 10$，$p_3 = 20$，$p_4 = 30$，$p_5 = 40$。另外，$r_2 = r_3 = r_4 = 15$。$P_2$ 和 $P_3$ 之间、$P_3$ 和 $P_4$ 之间、以及 $P_4$ 和 $P_5$ 之间的距离分别是 10，然而绳子的长度都是 15。所以这些绳子都不绷紧。如果 Joey 拉动 $R_2$ 一单位，$P_3$ 会向 $P_2$ 移动一单位（新的 $p_3 = 19$），而 $p_4$ 不受影响，因为 $R_3$ 并未绷紧。如果 Joey 继续多拉动 $R_2$ 四单位（总共五单位），则 $p_3 = 15$，$p_4 = 30$，$p_5 = 40$。此时，$R_3$ 绷紧，因为 $P_3$ 和 $P_4$ 之间的距离变成 $p_4 - p_3 = 30 - 15 = 15$，等于 $r_3$ 的长度。所以现在如果 Joey 再拉一单位，$P_3$ 和 $P_4$ 会同时移动（但 $P_5$ 不会，因为 $R_4$ 未绷紧）。新的位置将会是 $p_3 = 14$，$p_4 = 29$。

无

无

**本翻译由 AI 自动生成**