题解：P14439 [JOISC 2013] 考拉 / Koala

· · 题解

模拟赛搬了这道题，未切，于是写篇题解。

暴力

很简单的一个 DP，很明显只用考虑导师的家即可。设 f_i 表示到达第 i 个导师的家时可能的最大体力值。为了方便，把起点设为 0，终点设为 n+1。转移呼之欲出：

f_i=\max\limits_{j=0}^{i-1}~b_i+f_j-a\times \left \lceil \frac{t_i-t_j}{d} \right \rceil

答案很明显为 f_{n+1}。时间复杂度 O(n^2)。能过掉第一个子任务。期望得分二十。

正解

考虑优化。观察转移，我们考虑维护 f_j-a\times \left \lceil \frac{t_i-t_j}{d} \right \rceil 的最大值，但是由于其中包含 t_i，难以维护，所以我们考虑把 t_i 提出去。

设 s_i=\frac{t_i}{d} ，y_i=t_i \bmod d 。很容易发现，上面的转移可以化为：

f_i=\max\limits_{j=0}^{i-1}~b_i+f_j-a\times \left \lceil \frac{\left ( s_i\times d+y_i \right )-\left ( s_j\times d+y_j \right )}{d} \right \rceil f_i=\max\limits_{j=0}^{i-1}~b_i+f_j-a\times \left ( s_i-s_j + \left \lceil \frac{y_i-y_j}{d} \right \rceil \right )

很明显：0\le y_i< d。所以分类讨论向上取整取值。

所以转移式可化为：

很明显可用值域线段树维护 f_i+a\times s_i 的区间最大值。

由于 1\le d \le 10^9，所以我们使用动态开点线段树。

时间复杂度 O(n\log d)。