FIRST 题目大意 给你一些正整数，这些正整数为数轴上若干个点代表的数。现求：假设从原点出发，走m以内（包括m）的距离最多能够访问多少个点，输出m-每个点到达时已经走过的距离的累加和。
NEXT 前置结论 如图所示，首先我们假设数轴上有x,y两点，杀一个士兵的时间是 t i t_i ti ∵ t i ≡ 0 t_i \equiv 0 ti≡0 ∴不存在从远点跳过点 y y y直接奔向点 x x x存在最优解的可能性
AFTER THAT 解题思路 40分思路 排序+基于前置结论，进行dfs，普通可得40分，再优化一下可能能拿60分 100分思路 排序+动态规划 为了方便取，从小到大排序 既然不可能出现中间为断点的情况 那么我们想要最优解，我们已经死亡的士兵就一定是一个区间 状态易设： f i , j , 0 f_{i,j,0} fi,j,0表示区间 i i i~ j j j全部已经被杀死了,当前状态杀死的是 i i i（左边）最大值 f i , j , 1 f_{i,j,1} fi,j,1表示区间 i i i~ j j j全部已经被杀死了,当前状态杀死的是 j j j（右边）最大值
可得一个大概的转移式： f i , j , 0 = m a x ( f i + 1 , j , 0 + m − X ， f i + 1 , j , 1 + m − Y ) f_{i,j,0} = max(f_{i+1,j,0}+m-X，f_{i+1,j,1}+m-Y) fi,j,0=max(fi+1,j,0+m−X，fi+1,j,1+m−Y) f i , j , 1 = m a x ( f i , j − 1 , 0 + m − X ， f i , j − 1 , 1 + m − Y ) f_{i,j,1} = max(f_{i,j-1,0}+m-X，f_{i,j-1,1}+m-Y) fi,j,1=max(fi,j−1,0+m−X，fi,j−1,1+m−Y) 现在我们就是要求这个 X , Y X,Y X,Y分别是多少（即损耗时间） 我们可以尝试转换一个思路：
即假设你要杀 k k k个人，已经杀了 x x x个，那么你每走 1 1 1步，另外的生命值都-1.即总可以获得的收益减少了 ( k − x ) (k-x) (k−x) 走 t t t步同理 t ( k − x ) t(k-x) t(k−x) 带入原式得 X = ( a i + 1 − a i ) ⋅ ( k − j + i ) X=(a_{i+1}-a_i) \cdot (k-j+i) X=(ai+1−ai)⋅(k−j+i) Y = ( a j − a i ) ⋅ ( k − j + i ) Y=(a_{j}-a_i) \cdot (k-j+i) Y=(aj−ai)⋅(k−j+i) 由于 K K K没有，那我们直接枚举就完事了。
In The End
如果a数组里没有原点我们要补一个原点进去一起排序要注意 f f f数组的特判和初始值如果 j − i + 1 > k j-i+1>k j−i+1>k请及时break