自动搬运

查看原文

来自洛谷，原作者为

	UnyieldingTrilobite 直到世界 只剩下闪烁的黑白

搬运于2025-08-24 22:05:58，当前版本为作者最后更新于2022-08-10 20:02:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目 lnk。

这么好的题怎么没人写题解啊（迫

首先不难想到一个贪心：从最左（初始点）跳到最右，再跳到第二左，再跳到第二右……以此类推。但是这仅仅是一个感性理解上路程最远的走法，它需要一个证明。

以下不妨有 $0=h_0\lt h_1\lt h_2\lt h_3\lt\cdots\lt h_n$。注意到，我们其实仅仅需要证明最优情况下第一步从 $0$ 跳到 $h_n$ 即可（此后左右翻转可以证明第二步跳到 $h_1$，以此类推，整个贪心流程的正确性证明也就完成了）。

假设存在一种最优情况使得第一步不是从 $0$ 跳到 $h_n$ 而是跳到 $h_p$（$1\le p\le n-1$），那么我们分两类讨论：

1. $h_n$ 是终点

那么我们第一步改跳 $h_n$ 然后全程反转，则体力值耗费增加 $h_n^2-h_p^2>0$，矛盾。

2. $h_n$ 不是终点。

不妨 $h_n$ 跳向了 $h_q$。

那么我们第一步改跳 $h_n$，然后从 $h_p$ 到 $h_n$ 的跳跃全程反转，然后 $h_p$ 跳 $h_q$，则体力耗费增加 $h_n^2+(h_p-h_q)^2-h_p^2-(h_n-h_q)^2=2h_q(h_n-h_p)>0$，矛盾。

综上，第一步一定是从 $0$ 跳到 $h_n$，证毕。

代码非常好写，就不挂了。