萌新想了一会才想出来的,供以后没想通的同学们参考QAQ
如有错误请指出
一种可能的答案为:对于前x大的疲劳值,计算其总和,再加上前x大疲劳值中最大的路程。
为什么是“可能”的答案呢?也许不难发现,如果一个疲劳值很小,而其距离很大,有可能通过舍去一个前x大中最小的疲劳值,改成距离大的小疲劳值,能通过加上更多距离来实现更大的疲劳值。
即,从x的后面开始看,也会存在一个最大值,代表了选择x后某一个元素所能达到的最大疲劳值。
那为什么不能从后面取>1个的最大值,2个,3个,甚至更多个?
假设:舍去前x个中的两个最小值,取x之后的两个最大值
舍去的疲劳值:a[x]+a[x-1]
x之后的两个最大值:a[n]+a[m]+max(dis[n],dis[m])
分类讨论:
1.a[n]>a[m],dis[n]>dis[m]
这种情况下,a[n]+dis[n]就是后部分最大值,舍去两个后用a[m]替代了a[x-1],而a[m]<a[x-1],错误。
2.a[n]>a[m],dis[n]<dis[m]
可分为两种情况:a[n]+dis[n]>a[m]+dis[m],此时a[n]+dis[n]就是后部分最大值,舍去前面两个就是同样的用a[m]替代了a[x-1]。另一种方式同理。舍去更多值时同理。
那么就可以证明只有舍去最小的疲劳值,替代后半部分的一个最大值时有可能答案更大。