[JZOJ]2109 清兵线 题解

• 2020 年 10 月 6 日
• 筆記

## [JZOJ]2109 清兵线 题解
**FIRST 题目大意**
给你一些正整数，这些正整数为数轴上若干个点代表的数。现求：假设从原点出发，走m以内（包括m）的距离最多能够访问多少个点，输出m-每个点到达时已经走过的距离的累加和。
****
**NEXT 前置结论**
如图所示，首先我们假设数轴上有x,y两点，杀一个士兵的时间是$t_i$
∵$t_i \equiv 0$
∴**不存在**从远点跳过点$y$直接奔向点$x$存在最优解的可能性
****
**AFTER THAT 解题思路**
**40分思路**
排序+基于前置结论，进行dfs，普通可得40分，再优化一下可能能拿60分
**100分思路**
排序+动态规划
为了方便取，从小到大排序
既然不可能出现中间为断点的情况
那么我们想要最优解，我们已经死亡的士兵就一定是一个**区间**
状态易设：
$f_{i,j,0}$表示区间$i$~$j$全部已经被杀死了,当前状态杀死的是$i$（左边）最大值
$f_{i,j,1}$表示区间$i$~$j$全部已经被杀死了,当前状态杀死的是$j$（右边）最大值

可得一个大概的转移式：
$f_{i,j,0} = max(f_{i+1,j,0}+m-X，f_{i+1,j,1}+m-Y)$
$f_{i,j,1} = max(f_{i,j-1,0}+m-X，f_{i,j-1,1}+m-Y)$
现在我们就是要求这个 $X,Y$分别是多少（即损耗时间）
我们可以尝试转换一个思路：

即假设你要杀$k$个人，已经杀了$x$个，那么你每走$1$步，另外的生命值都-1.即总可以获得的收益减少了$(k-x)$
走$t$步同理$t(k-x)$
带入原式得
$X=(a_{i+1}-a_i) \cdot (k-j+i)$
$Y=(a_{j}-a_i) \cdot (k-j+i)$
由于$K$没有，那我们直接枚举就完事了。
***
**In The End**

1. 如果a数组里没有原点我们要补一个原点进去一起排序
2. 要注意$f$数组的特判和初始值
3. 如果$j-i+1>k$请及时break