前几天做了一道打卡题，205 做完了之后我就去了 www.luogu.com.cn 上面一搜，发现是2015年普及组复赛第三题，我又发现，前两题都是入门题……当时我就去挑战了一下第四题……没什么思路,用贪心干了60分出来.

这次又一想竟然想出来了

进入正题: 既然贪心会超时，不如用前缀和预处理，就能节省时间 我又想到既然距离只最大值有关系，那么就不用考虑太多的距离问题了

无非只有两种情况 第一种是挑疲劳值大的推销 另外一种情况就是挑最大的疲劳值n-1个及路径最远的那个 在这两个里面挑一个总疲劳值更大的 （由于距离所产生的疲劳只和最大的距离有关系，所以就不用考虑其他情况了，当时我没想到这点。）

首先，我们需要按照疲劳值大小排序 然后需要进行三个预处理，分别是疲劳值的前缀和 ，前i个的最大距离×2，以及后i个距离×2+疲劳值 程序就可以做出来了

具体程序略

比较公式略