题解：P7057 [NWRRC2015] Journey to the “The World’s Start”
_Flame_
·
·
题解
solution
先让 t 减去 n-1。
发现一个显然的性质，如果长度为 r_i 的车票可行，那么比他大的都可以。
二分转化问题，如何求第 x 张车票的最小时间。
设 dp_i 为在 i 点下车的最小时间。假设现在在用第 x 张车票，明显有转移 dp_i=\min\limits_{j=i-x}^{i-1}dp_j+d_i。
区间求最小值，直接线段树优化。
注意转移的时候 j 的范围下界要和 1 取较大值。