mengbierr

一个蒟蒻的博客

4月21

BZOJ5286&luogu4425&LOJ2495: [Hnoi2018]转盘

可以把问题转换成第i个点在 t_i 消失,问找最早出发时间,最优策略是一直向前走,这就等价于在起点一直等待然后直接走到最后不停止。
将数组增长一倍,答案变成:
min_{i=1}^n {max_{j>=1}t_{i+j}+n-j-1}
p_i=t_i-i 式子等价于
min_{i=1}^n {i+max_{j>=i}{p_j}}
维护区间最大值和式子最小值就行了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注