水题解

· · 题解

题目 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），那么我们分两类讨论：

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

不妨 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，证毕。

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