机器人回收电池——两种区间 DP 解法
一、先把题目说简单一点
有一个机器人站在位置 sss。
地上有 nnn 块电池，第 iii 块电池：
* 在位置 xix_ixi
* 捡到后可以增加 eie_iei 点能量
机器人每走 111 格，就要花掉 111 点能量，而且走路的时候能量不能变成负数。
现在要把所有电池都捡完，问：
> 机器人一开始最少要带多少能量？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、最重要的观察：捡过的电池一定可以看成一个连续区间
我们先把所有电池按照位置从小到大排序。
再把机器人的起点 sss 也放进去，把它看成一块：
* 位置是 sss
* 能量是 000
的“假电池”。
假设排完序以后是：
x1<x2<⋯<xmx_1<x_2<\cdots<x_m x1 <x2 <⋯<xm
其中：
m=n+1m=n+1 m=n+1
假设起点 sss 排在第 kkk 个位置。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
为什么可以做区间 DP 呢？
比如机器人已经捡完了第 lll 块到第 rrr 块：
[l,r][l,r] [l,r]
那么接下来如果还想往左边捡，最先遇到的一定是第 l−1l-1l−1 块。
如果想往右边捡，最先遇到的一定是第 r+1r+1r+1 块。
你不可能从第 lll 块直接跑去第 l−2l-2l−2 块，却故意路过第 l−1l-1l−1 块不捡。
所以机器人已经捡过的电池，可以一直看成一个连续区间：
[l,r][l,r] [l,r]
而机器人此时只需要考虑站在：
* 区间左端 xlx_lxl
* 区间右端 xrx_rxr
中的哪一个位置。
这就是整道题最重要的地方。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解法一：二分答案 + 正向区间 DP
三、二分什么？
我们直接猜：
> 如果机器人最开始有 EEE 点能量，它能不能捡完所有电池？
如果 EEE 点能量可以完成任务，那么：
E+1,E+2,E+3,…E+1,E+2,E+3,\dots E+1,E+2,E+3,…
肯定也都可以。
也就是说答案具有很明显的单调性：
所以可以二分最小的可行初始能量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、固定初始能量以后，怎么判断能不能完成？
假设我们现在已经猜好了初始能量 EEE。
定义：
dp[l][r][0]dp[l][r][0] dp[l][r][0]
表示：
> 已经把区间 [l,r][l,r][l,r] 内的电池全部捡完，并且现在站在左端 xlx_lxl 时，最多还能剩多少能量。
同理：
dp[l][r][1]dp[l][r][1] dp[l][r][1]
表示站在右端 xrx_rxr 时最多还能剩多少能量。
为什么保存“最多剩多少能量”？
因为在同一个状态下：
> 剩下的能量当然越多越好。
所以如果有很多种路线能到达同一个状态，我们只留下剩余能量最多的那一种。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、初始状态
机器人一开始站在 sss。
假设 sss 在排序以后的位置是 kkk。
因此一开始区间只有：
[k,k][k,k] [k,k]
机器人身上有 EEE 点能量：
dp[k][k][0]=dp[k][k][1]=Edp[k][k][0]=dp[k][k][1]=E dp[k][k][0]=dp[k][k][1]=E
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、状态怎么转移？
假设现在已经捡完：
[l,r][l,r] [l,r]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
情况 1：现在站在左端 XLX_LXL
往左走
下一块电池是第 l−1l-1l−1 块。
需要走：
xl−xl−1x_l-x_{l-1} xl −xl−1
这么远。
如果当前能量不少于这段距离，就可以过去。
到达以后：
1. 先消耗路程对应的能量；
2. 再获得第 l−1l-1l−1 块电池的 el−1e_{l-1}el−1 点能量。
所以：
dp[l−1][r][0]dp[l-1][r][0] dp[l−1][r][0]
可以用：
dp[l][r][0]−(xl−xl−1)+el−1dp[l][r][0]-(x_l-x_{l-1})+e_{l-1} dp[l][r][0]−(xl −xl−1 )+el−1
更新。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
往右走
如果现在站在 xlx_lxl ，要去右边的新电池 xr+1x_{r+1}xr+1 ，距离就是：
xr+1−xlx_{r+1}-x_l xr+1 −xl
因此可以更新：
dp[l][r+1][1]dp[l][r+1][1] dp[l][r+1][1]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
情况 2：现在站在右端 XRX_RXR
完全一样。
往左：
距离为：
xr−xl−1x_r-x_{l-1} xr −xl−1
往右：
距离为：
xr+1−xrx_{r+1}-x_r xr+1 −xr
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、为什么到电池以后加的能量不能帮我们“补路费”？
这一点很重要。
比如：
* 当前有 333 点能量
* 电池距离你 555
* 那块电池能提供 100100100 点能量
你还是走不到。
因为你必须先到达电池的位置，才能拿到它的能量。
所以转移之前一定要先判断：
当前能量≥距离当前能量\ge 距离 当前能量≥距离
然后才能：
当前能量−距离+电池能量当前能量-距离+电池能量 当前能量−距离+电池能量
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、怎样判断这个 EEE 是否可行？
最后如果能够到达完整区间：
[1,m][1,m] [1,m]
就说明所有电池都捡完了。
因此只要：
dp[1][m][0]≥0dp[1][m][0]\ge0 dp[1][m][0]≥0
或者：
dp[1][m][1]≥0dp[1][m][1]\ge0 dp[1][m][1]≥0
就说明这个初始能量 EEE 可行。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、二分上界怎么取？
其实就算所有电池都不给能量，我们只要准备足够多的初始能量，也一定能够走完。
设最左边电池的位置是 LLL，最右边是 RRR。
如果：
s≤Ls\le L s≤L
一路向右走即可，需要：
R−sR-s R−s
如果：
s≥Rs\ge R s≥R
一路向左走即可，需要：
s−Ls-L s−L
如果起点在中间，可以：
先走左边，再走最右边：
2(s−L)+(R−s)2(s-L)+(R-s) 2(s−L)+(R−s)
也可以：
先走右边，再走最左边：
2(R−s)+(s−L)2(R-s)+(s-L) 2(R−s)+(s−L)
取较小值即可作为二分上界。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、解法一代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、解法一复杂度
一次 check() 要枚举所有区间，所以时间复杂度为：
O(n2)O(n^2) O(n2)
外面还有一次二分。
因为坐标最大只有 10910^9109，二分次数大约只有几十次。
总时间复杂度：
O(n2logC)O(n^2\log C) O(n2logC)
其中 CCC 表示答案的大小。
空间复杂度：
O(n2)O(n^2) O(n2)
对于：
n≤300n\le300 n≤300
完全没有问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解法二：直接逆向 DP
这个方法更加漂亮，因为：
> 不需要二分答案。
它直接计算机器人一开始最少需要多少能量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十二、什么叫“逆向”？
刚才第一种方法的思路是：
> 我现在有这么多能量，看看接下来能不能走。
第二种方法反过来想：
> 如果我以后还需要这么多能量，那么我现在至少要准备多少能量？
我们先来看一个特别重要的小问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十三、一个最关键的小公式
假设机器人现在准备去下一块电池。
距离这块电池还有：
dd d
这块电池可以增加：
ee e
点能量。
而捡完这块电池以后，剩下的任务要求机器人至少还拥有：
needneed need
点能量。
问：
> 出发之前至少应该有多少能量？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
假设出发之前有 EEE 点。
首先，你至少要能够走到电池那里：
E≥dE\ge d E≥d
到达以后剩下：
E−dE-d E−d
再捡到电池，变成：
E−d+eE-d+e E−d+e
而接下来的任务要求至少有 needneedneed：
E−d+e≥needE-d+e\ge need E−d+e≥need
也就是：
E≥need+d−eE\ge need+d-e E≥need+d−e
所以我们同时需要：
E≥dE\ge d E≥d
以及：
E≥need+d−eE\ge need+d-e E≥need+d−e
因此：
E=max(d,need+d−e)E=\max(d,need+d-e) E=max(d,need+d−e)
还可以写成一个更好看的形式：
E=d+max(0,need−e)\boxed{E=d+\max(0,need-e)} E=d+max(0,need−e)
这就是逆向 DP 最重要的公式。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十四、这个公式怎么理解？
比如前面还有一段路需要你拥有 101010 点能量。
现在下一块电池能够补充 777 点。
那么这块电池可以帮你承担其中的 777 点。
你自己只需要额外准备：
10−7=310-7=3 10−7=3
点。
如果这块电池直接给了 100100100 点，而未来只需要 101010 点，那么它已经完全够用了。
你不需要为了未来再额外准备能量。
所以有：
max(0,need−e)\max(0,need-e) max(0,need−e)
但不管电池多厉害，你至少还是得先走到它那里。
因此还必须准备距离 ddd 对应的能量。
最终就是：
d+max(0,need−e)d+\max(0,need-e) d+max(0,need−e)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十五、逆向 DP 的状态
还是使用区间：
[l,r][l,r] [l,r]
定义：
dp[l][r][0]dp[l][r][0] dp[l][r][0]
表示：
> 第 lll 到第 rrr 个位置都已经处理好了，现在机器人站在 xlx_lxl ，如果想把剩下所有电池全部捡完，当前至少需要有多少能量。
同理：
dp[l][r][1]dp[l][r][1] dp[l][r][1]
表示机器人当前站在 xrx_rxr 时，至少需要多少能量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注意它和第一种做法正好相反。
第一种 DP 保存的是：
> 我现在最多还剩多少能量。
第二种 DP 保存的是：
> 我现在至少应该拥有多少能量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十六、逆向 DP 从哪里开始？
如果：
[1,m][1,m] [1,m]
已经全部处理完了，也就是说所有电池都已经捡完。
那么后面什么都不用做了。
所以需要的能量是：
00 0
即：
dp[1][m][0]=dp[1][m][1]=0dp[1][m][0]=dp[1][m][1]=0 dp[1][m][0]=dp[1][m][1]=0
接下来我们不断缩小区间。
最后一直算到：
[k,k][k,k] [k,k]
这里就是机器人的起点。
由于起点的“假电池”能量为 000，所以：
dp[k][k]dp[k][k] dp[k][k]
就是机器人最开始至少需要准备的能量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十七、逆向状态转移
假设我们正在计算：
dp[l][r][0]dp[l][r][0] dp[l][r][0]
也就是机器人现在站在左端 xlx_lxl 。
它下一步有两种选择。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
选择 1：去左边的第 L−1L-1L−1 块电池
距离：
d=xl−xl−1d=x_l-x_{l-1} d=xl −xl−1
到达以后，新状态为：
[l−1,r][l-1,r] [l−1,r]
并且站在左端。
未来所需能量为：
dp[l−1][r][0]dp[l-1][r][0] dp[l−1][r][0]
第 l−1l-1l−1 块电池提供：
el−1e_{l-1} el−1
所以根据刚才的公式：
d+max(0,dp[l−1][r][0]−el−1)d+\max(0,dp[l-1][r][0]-e_{l-1}) d+max(0,dp[l−1][r][0]−el−1 )
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
选择 2：去右边的第 R+1R+1R+1 块电池
因为当前站在 xlx_lxl ，所以要走：
d=xr+1−xld=x_{r+1}-x_l d=xr+1 −xl
新状态是：
[l,r+1][l,r+1] [l,r+1]
并站在右端。
所需能量：
dp[l][r+1][1]dp[l][r+1][1] dp[l][r+1][1]
所以当前最少需要：
d+max(0,dp[l][r+1][1]−er+1)d+\max(0,dp[l][r+1][1]-e_{r+1}) d+max(0,dp[l][r+1][1]−er+1 )
两种路线里面选更好的即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十八、站在右端也是一样
如果现在站在 xrx_rxr ：
去左边：
距离：
xr−xl−1x_r-x_{l-1} xr −xl−1
去右边：
距离：
xr+1−xrx_{r+1}-x_r xr+1 −xr
仍然套：
d+max(0,need−e)d+\max(0,need-e) d+max(0,need−e)
这个公式即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十九、为什么逆向 DP 不需要保存“已经捡到的电池总能量”？
这是这个方法很漂亮的地方。
比如某些电池已经捡完了，那么它们给你的能量已经变成了机器人当前拥有的能量的一部分。
所以我们根本不用管以前发生过什么。
我们只问：
> 从现在开始，要完成后面的任务，我当前至少需要多少能量？
之前拿到多少电池、走了多少路，都不重要了。
因此状态只需要：
[l,r][l,r] [l,r]
以及机器人站在哪一端。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二十、逆向 DP 代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二十一、逆向 DP 为什么要从大区间往小区间算？
例如我们想计算：
dp[l][r]dp[l][r] dp[l][r]
它需要知道：
dp[l−1][r]dp[l-1][r] dp[l−1][r]
或者：
dp[l][r+1]dp[l][r+1] dp[l][r+1]
这两个区间都比：
[l,r][l,r] [l,r]
更大。
所以必须：
> 先算大区间，再算小区间。
因此区间长度 len 要从大到小枚举：
这就是这里“逆向”的另一层含义。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二十二、两种方法对比
方法 DP 中保存什么 时间复杂度 特点 二分 + 正向 DP 当前最多剩多少能量 O(n2logC)O(n^2\log C)O(n2logC) 比较直观，容易从“模拟机器人走路”理解 直接逆向 DP 当前最少需要多少能量 O(n2)O(n^2)O(n2) 更快、更巧，不需要二分
其中空间复杂度都是：
O(n2)O(n^2) O(n2)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二十三、最推荐记住的两个状态
如果以后再次遇到这种：
> 有资源、移动会消耗资源、到某些位置又能补充资源
的问题，可以尝试两种思考方式。
正着想
> 我已经走到这里了，最多还剩多少资源？
这道题就是：
dp[l][r][0/1]=最大剩余能量dp[l][r][0/1]=最大剩余能量 dp[l][r][0/1]=最大剩余能量
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
反着想
> 为了完成后面的任务，我现在至少需要多少资源？
这道题就是：
dp[l][r][0/1]=最少所需能量dp[l][r][0/1]=最少所需能量 dp[l][r][0/1]=最少所需能量
而逆向 DP 中最核心的式子只有一个：
d+max(0,need−e)\boxed{d+\max(0,need-e)} d+max(0,need−e)
其中：
* ddd：走到下一块电池的距离
* eee：下一块电池能够补充的能量
* needneedneed：捡完这块电池以后，完成剩余任务至少需要的能量
只要真正理解这个式子，第二种做法基本就理解了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二十四、一句话总结整道题
先把起点也当成一个能量为 000 的点，按坐标排序。
由于机器人向左右扩展时，下一块能遇到的电池一定是当前区间旁边的电池，所以：
> 已经回收的部分可以用一个区间 [l,r][l,r][l,r] 表示。
于是：
* 正向 DP：求“走到这里最多还剩多少能量”，再配合二分答案；
* 逆向 DP：求“从这里开始至少需要多少能量”，直接得到最终答案。
如果只从代码长度和复杂度来看，更推荐掌握第二种逆向区间 DP。
