AGC012E Camel and Oases

题意：给定 个绿洲，坐标为 。

初始背包容积为 升且满水。每到达一个绿洲，可以将背包加满水。

可以利用下列两个操作来旅行：

走路，行走距离为 时，需要消耗 升水。任意时刻拥有的水的数量不能为负数。

跳跃，令 为你当前拥有的水量，若 ，则你可以跳跃至任意一个绿洲，然后重置容积上界和所拥有的水量为 。

对于每一个 ，判定当你在第 个绿洲作为起点时，你能否遍历其他所有绿洲。

，时限 。

---

• 跳跃只能进行 次。

• 给定背包容积时，从某点 出发能到达的绿洲是一段连续区间。

  各个点的区间要么不交，要么相同。

于是，对 类背包容积，分别求出从每个点出发能到达的区间。

然后问题变为：

在每类区间集合中各选出一个，且第一种的区间必选 ，能否覆盖全集。

考虑状压 ，记 表示在类 中选了区间，覆盖的最长前缀。

转移时，枚举某一类，然后取左端点在 内的最靠右的区间。

复杂度为 。

但题目要求钦定起点（所在的区间），那就要加一维，复杂度变为 ，无法承受。

我们发现，若第一类有超过 个本质不同的区间，则必然无解。故实际上加上的那一维大小只需要为 。

复杂度 。

还有一个复杂度更好的做法，先不考虑起点，计算出 分别表示最长前缀 / 后缀。

然后枚举起点的区间，再枚举前缀集合 ，后缀则取补集。

这样复杂度就是 。