专栏文章

题解：P7057 [NWRRC2015] Journey to the “The World’s Start”

__Flame_
P7057题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir1m81g
此快照首次捕获于
2025/12/04 14:16
3 个月前
此快照最后确认于
2025/12/04 14:16
3 个月前
查看原文

solution

先让 tt 减去 n−1n-1。
发现一个显然的性质，如果长度为 rir_i 的车票可行，那么比他大的都可以。
二分转化问题，如何求第 xx 张车票的最小时间。
设 dpidp_i 为在 ii 点下车的最小时间。假设现在在用第 xx 张车票，明显有转移 dpi=min⁡j=i−xi−1dpj+didp_i=\min\limits_{j=i-x}^{i-1}dp_j+d_i。
区间求最小值，直接线段树优化。
注意转移的时候 jj 的范围下界要和 11 取较大值。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...