前言

这题真难吧，机房一车人没一个会做？？

思路

首先你如果不对这个题进行什么深入挖掘，八成是想不出任何多项式做法的啊，然后注意到这个数据范围，在不存在可行的贪心策略的情况下，基本就是让你去设计一个 O(n2)\mathcal{O(n^2)} 的 dp 没跑了。

但他这个关灯的轨迹看起来非常的神秘，无规律可循，怎么才能把它转化成一个便于 dp 的形式呢？

发现一个事情：我们的起点是最左边，如果从一开始没有一路关到底的话，中间没有被关的灯迟早还是需要再折返回来关一次。

然后看到题目里给的限制是必须在 ≥t\geq t 的时刻关掉区间里的灯，因此拖到折返的时候再关被空出来的地方后面的灯就是更划算的。那么你现在已经关掉了前缀的一段灯，如果从某个位置开始停止关闭前缀的灯，还需要向右走吗？那必然是需要的，否则直接从头关到尾不就好了吗（感觉像废话文学 T T）。那么此时向右走的目标就很明确了，即走到最右边去关闭后缀的一串灯，后面的过程与刚开始的时候类似。

由此我们便描绘出了本题的重要结论：任意时刻场上未被关闭的灯一定构成一段连续区间。到这里设计 dp 就变得不那么无从下手了。

设 fl,r,0f_{l,r,0} 为关掉了除 (l,r](l,r] 以外的所有灯、当前位置为 ll 所需的最小时间，fl,r,1f_{l,r,1} 为关掉了 [l,r)[l,r) 外的所有灯，当前位置在 rr 所需的最小时间。于是有转移：

fl,r,0=max⁡(min⁡(fl−1,r,0+dis⁡(l−1,l),fl,r+1,1+dis⁡(r+1,l)),tl)f_{l,r,0}=\max(\min(f_{l-1,r,0}+\operatorname{dis}(l-1,l),f_{l,r+1,1}+\operatorname{dis}(r+1,l)),t_l)

fl,r,1=max⁡(min⁡(fl,r+1,1+dis⁡(r+1,r),fl−1,r,0+dis⁡(l−1,r)),tr)f_{l,r,1}=\max(\min(f_{l,r+1,1}+\operatorname{dis}(r+1,r),f_{l-1,r,0}+\operatorname{dis}(l-1,r)),t_r)

其中 dis⁡(i,j)\operatorname{dis}(i,j) 代表从 ii 走到 jj 的距离，txt_x 代表允许关掉第 xx 个灯的最晚时间。解释一下式子的意义：以当前在 ll 即这一步关掉了 ll 处的灯的情况为例，则上一步要么是从 l−1l-1 顺着走过来，要么就是关完 r+1r+1 后折返回来。

具体实现上先把所有关键点离散化一下，然后暴力对所有区间的限制取 max，因为有 10410^4 个点，两维 dp 数组可能开不太下，由于 l,rl,r 的转移只与 l−1,rl-1,r 和 l,r+1l,r+1 的状态有关，可以倒着枚举 rr 然后滚动数组一下。由于关灯过程一定在一个地方结束，答案就是所有 fi,i,0/1f_{i,i,0/1} 取 min。

时间复杂度 O(n2)\mathcal{O}(n^2)。