机器人回收电池解题思路

吴老师

2026-08-16 09:13:13

发布于：广东

21阅读

0回复

0点赞

机器人回收电池——两种区间 DP 解法

一、先把题目说简单一点

有一个机器人站在位置 $s$ 。

地上有 $n$ 块电池，第 $i$ 块电池：

在位置 $x_i$
捡到后可以增加 $e_i$ 点能量

机器人每走 $1$ 格，就要花掉 $1$ 点能量，而且走路的时候能量不能变成负数。

现在要把所有电池都捡完，问：

机器人一开始最少要带多少能量？

二、最重要的观察：捡过的电池一定可以看成一个连续区间

我们先把所有电池按照位置从小到大排序。

再把机器人的起点 $s$ 也放进去，把它看成一块：

位置是 $s$
能量是 $0$

的“假电池”。

假设排完序以后是：

$x_1<x_2<\cdots<x_m$

其中：

$m=n+1$

假设起点 $s$ 排在第 $k$ 个位置。

为什么可以做区间 DP 呢？

比如机器人已经捡完了第 $l$ 块到第 $r$ 块：

$[l,r]$

那么接下来如果还想往左边捡，最先遇到的一定是第 $l-1$ 块。

如果想往右边捡，最先遇到的一定是第 $r+1$ 块。

你不可能从第 $l$ 块直接跑去第 $l-2$ 块，却故意路过第 $l-1$ 块不捡。

所以机器人已经捡过的电池，可以一直看成一个连续区间：

$[l,r]$

而机器人此时只需要考虑站在：

区间左端 $x_l$
区间右端 $x_r$

中的哪一个位置。

这就是整道题最重要的地方。

解法一：二分答案 + 正向区间 DP

三、二分什么？

我们直接猜：

如果机器人最开始有 $E$ 点能量，它能不能捡完所有电池？

如果 $E$ 点能量可以完成任务，那么：

$E+1,E+2,E+3,\dots$

肯定也都可以。

也就是说答案具有很明显的单调性：

不可以 不可以 不可以 可以 可以 可以 可以

所以可以二分最小的可行初始能量。

四、固定初始能量以后，怎么判断能不能完成？

假设我们现在已经猜好了初始能量 $E$ 。

定义：

$dp[l][r][0]$

表示：

已经把区间 $[l,r]$ 内的电池全部捡完，并且现在站在左端 $x_l$ 时，最多还能剩多少能量。

同理：

$dp[l][r][1]$

表示站在右端 $x_r$ 时最多还能剩多少能量。

为什么保存“最多剩多少能量”？

因为在同一个状态下：

剩下的能量当然越多越好。

所以如果有很多种路线能到达同一个状态，我们只留下剩余能量最多的那一种。

五、初始状态

机器人一开始站在 $s$ 。

假设 $s$ 在排序以后的位置是 $k$ 。

因此一开始区间只有：

$[k,k]$

机器人身上有 $E$ 点能量：

$dp[k][k][0]=dp[k][k][1]=E$

六、状态怎么转移？

假设现在已经捡完：

$[l,r]$

情况 1：现在站在左端 $x_l$

往左走

下一块电池是第 $l-1$ 块。

需要走：

$x_l-x_{l-1}$

这么远。

如果当前能量不少于这段距离，就可以过去。

到达以后：

先消耗路程对应的能量；
再获得第 $l-1$ 块电池的 $e_{l-1}$ 点能量。

所以：

$dp[l-1][r][0]$

可以用：

$dp[l][r][0]-(x_l-x_{l-1})+e_{l-1}$

更新。

往右走

如果现在站在 $x_l$ ，要去右边的新电池 $x_{r+1}$ ，距离就是：

$x_{r+1}-x_l$

因此可以更新：

$dp[l][r+1][1]$

情况 2：现在站在右端 $x_r$

完全一样。

往左：

距离为：

$x_r-x_{l-1}$

往右：

距离为：

$x_{r+1}-x_r$

七、为什么到电池以后加的能量不能帮我们“补路费”？

这一点很重要。

比如：

当前有 $3$ 点能量
电池距离你 $5$
那块电池能提供 $100$ 点能量

你还是走不到。

因为你必须先到达电池的位置，才能拿到它的能量。

所以转移之前一定要先判断：

$当前能量\ge 距离$

然后才能：

$当前能量-距离+电池能量$

八、怎样判断这个 $E$ 是否可行？

最后如果能够到达完整区间：

$[1,m]$

就说明所有电池都捡完了。

因此只要：

$dp[1][m][0]\ge0$

或者：

$dp[1][m][1]\ge0$

就说明这个初始能量 $E$ 可行。

九、二分上界怎么取？

其实就算所有电池都不给能量，我们只要准备足够多的初始能量，也一定能够走完。

设最左边电池的位置是 $L$ ，最右边是 $R$ 。

如果：

$s\le L$

一路向右走即可，需要：

$R-s$

如果：

$s\ge R$

一路向左走即可，需要：

$s-L$

如果起点在中间，可以：

先走左边，再走最右边：

$2(s-L)+(R-s)$

也可以：

先走右边，再走最左边：

$2(R-s)+(s-L)$

取较小值即可作为二分上界。

十、解法一代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 305;
using ll = long long;

struct Node {
	ll x, e;
	bool st;
} a[N];

int n, m, k;
ll s;
ll x[N], e[N];
ll dp[N][N][2];

bool cmp(Node a, Node b) {
	return a.x < b.x;
}

bool check(ll E) {
	memset(dp, -1, sizeof dp);
	dp[k][k][0] = dp[k][k][1] = E;

	for(int len = 1; len <= m; len++) {
		for(int l = 1; l + len - 1 <= m; l++) {
			int r = l + len - 1;

			if(!(l <= k && k <= r)) continue;

			if(dp[l][r][0] >= 0) {
				if(l > 1) {
					ll d = x[l] - x[l - 1];
					if(dp[l][r][0] >= d) {
						dp[l - 1][r][0] = max(
							dp[l - 1][r][0],
							dp[l][r][0] - d + e[l - 1]
						);
					}
				}

				if(r < m) {
					ll d = x[r + 1] - x[l];
					if(dp[l][r][0] >= d) {
						dp[l][r + 1][1] = max(
							dp[l][r + 1][1],
							dp[l][r][0] - d + e[r + 1]
						);
					}
				}
			}

			if(dp[l][r][1] >= 0) {
				if(l > 1) {
					ll d = x[r] - x[l - 1];
					if(dp[l][r][1] >= d) {
						dp[l - 1][r][0] = max(
							dp[l - 1][r][0],
							dp[l][r][1] - d + e[l - 1]
						);
					}
				}

				if(r < m) {
					ll d = x[r + 1] - x[r];
					if(dp[l][r][1] >= d) {
						dp[l][r + 1][1] = max(
							dp[l][r + 1][1],
							dp[l][r][1] - d + e[r + 1]
						);
					}
				}
			}
		}
	}

	return dp[1][m][0] >= 0 || dp[1][m][1] >= 0;
}

int main() {
	cin >> n >> s;

	ll mn = (ll)4e18, mx = -1;

	for(int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].e;
		a[i].st = false;
		mn = min(mn, a[i].x);
		mx = max(mx, a[i].x);
	}

	a[n + 1] = {s, 0, true};

	m = n + 1;

	sort(a + 1, a + m + 1, cmp);

	for(int i = 1; i <= m; i++) {
		x[i] = a[i].x;
		e[i] = a[i].e;
		if(a[i].st) k = i;
	}

	ll l = 0, r;

	if(s <= mn) {
		r = mx - s;
	} else if(s >= mx) {
		r = s - mn;
	} else {
		r = min(
			2 * (s - mn) + (mx - s),
			2 * (mx - s) + (s - mn)
		);
	}

	while(l < r) {
		ll mid = (l + r) / 2;

		if(check(mid)) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}

	cout << l;

	return 0;
}

十一、解法一复杂度

一次 check() 要枚举所有区间，所以时间复杂度为：

$O(n^2)$

外面还有一次二分。

因为坐标最大只有 $10^9$ ，二分次数大约只有几十次。

总时间复杂度：

$O(n^2\log C)$

其中 $C$ 表示答案的大小。

空间复杂度：

$O(n^2)$

对于：

$n\le300$

完全没有问题。

解法二：直接逆向 DP

这个方法更加漂亮，因为：

不需要二分答案。

它直接计算机器人一开始最少需要多少能量。

十二、什么叫“逆向”？

刚才第一种方法的思路是：

我现在有这么多能量，看看接下来能不能走。

第二种方法反过来想：

如果我以后还需要这么多能量，那么我现在至少要准备多少能量？

我们先来看一个特别重要的小问题。

十三、一个最关键的小公式

假设机器人现在准备去下一块电池。

距离这块电池还有：

$d$

这块电池可以增加：

$e$

点能量。

而捡完这块电池以后，剩下的任务要求机器人至少还拥有：

$need$

点能量。

问：

出发之前至少应该有多少能量？

假设出发之前有 $E$ 点。

首先，你至少要能够走到电池那里：

$E\ge d$

到达以后剩下：

$E-d$

再捡到电池，变成：

$E-d+e$

而接下来的任务要求至少有 $need$ ：

$E-d+e\ge need$

也就是：

$E\ge need+d-e$

所以我们同时需要：

$E\ge d$

以及：

$E\ge need+d-e$

因此：

$E=\max(d,need+d-e)$

还可以写成一个更好看的形式：

$\boxed{E=d+\max(0,need-e)}$

这就是逆向 DP 最重要的公式。

十四、这个公式怎么理解？

比如前面还有一段路需要你拥有 $10$ 点能量。

现在下一块电池能够补充 $7$ 点。

那么这块电池可以帮你承担其中的 $7$ 点。

你自己只需要额外准备：

$10-7=3$

点。

如果这块电池直接给了 $100$ 点，而未来只需要 $10$ 点，那么它已经完全够用了。

你不需要为了未来再额外准备能量。

所以有：

$\max(0,need-e)$

但不管电池多厉害，你至少还是得先走到它那里。

因此还必须准备距离 $d$ 对应的能量。

最终就是：

$d+\max(0,need-e)$

十五、逆向 DP 的状态

还是使用区间：

$[l,r]$

定义：

$dp[l][r][0]$

表示：

第 $l$ 到第 $r$ 个位置都已经处理好了，现在机器人站在 $x_l$ ，如果想把剩下所有电池全部捡完，当前至少需要有多少能量。

同理：

$dp[l][r][1]$

表示机器人当前站在 $x_r$ 时，至少需要多少能量。

注意它和第一种做法正好相反。

第一种 DP 保存的是：

我现在最多还剩多少能量。

第二种 DP 保存的是：

我现在至少应该拥有多少能量。

十六、逆向 DP 从哪里开始？

如果：

$[1,m]$

已经全部处理完了，也就是说所有电池都已经捡完。

那么后面什么都不用做了。

所以需要的能量是：

$0$

即：

$dp[1][m][0]=dp[1][m][1]=0$

接下来我们不断缩小区间。

最后一直算到：

$[k,k]$

这里就是机器人的起点。

由于起点的“假电池”能量为 $0$ ，所以：

$dp[k][k]$

就是机器人最开始至少需要准备的能量。

十七、逆向状态转移

假设我们正在计算：

$dp[l][r][0]$

也就是机器人现在站在左端 $x_l$ 。

它下一步有两种选择。

选择 1：去左边的第 $l-1$ 块电池

距离：

$d=x_l-x_{l-1}$

到达以后，新状态为：

$[l-1,r]$

并且站在左端。

未来所需能量为：

$dp[l-1][r][0]$

第 $l-1$ 块电池提供：

$e_{l-1}$

所以根据刚才的公式：

$d+\max(0,dp[l-1][r][0]-e_{l-1})$

选择 2：去右边的第 $r+1$ 块电池

因为当前站在 $x_l$ ，所以要走：

$d=x_{r+1}-x_l$

新状态是：

$[l,r+1]$

并站在右端。

所需能量：

$dp[l][r+1][1]$

所以当前最少需要：

$d+\max(0,dp[l][r+1][1]-e_{r+1})$

两种路线里面选更好的即可。

十八、站在右端也是一样

如果现在站在 $x_r$ ：

去左边：

距离：

$x_r-x_{l-1}$

去右边：

距离：

$x_{r+1}-x_r$

仍然套：

$d+\max(0,need-e)$

这个公式即可。

十九、为什么逆向 DP 不需要保存“已经捡到的电池总能量”？

这是这个方法很漂亮的地方。

比如某些电池已经捡完了，那么它们给你的能量已经变成了机器人当前拥有的能量的一部分。

所以我们根本不用管以前发生过什么。

我们只问：

从现在开始，要完成后面的任务，我当前至少需要多少能量？

之前拿到多少电池、走了多少路，都不重要了。

因此状态只需要：

$[l,r]$

以及机器人站在哪一端。

二十、逆向 DP 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 305;
const long long INF = (long long)4e18;
using ll = long long;

struct Node {
	ll x, e;
	bool st;
} a[N];

int n, m, k;
ll s;
ll x[N], e[N];
ll dp[N][N][2];

bool cmp(Node a, Node b) {
	return a.x < b.x;
}

int main() {
	cin >> n >> s;

	for(int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].e;
		a[i].st = false;
	}

	a[n + 1] = {s, 0, true};

	m = n + 1;

	sort(a + 1, a + m + 1, cmp);

	for(int i = 1; i <= m; i++) {
		x[i] = a[i].x;
		e[i] = a[i].e;
		if(a[i].st) k = i;
	}

	for(int l = 1; l <= m; l++) {
		for(int r = 1; r <= m; r++) {
			dp[l][r][0] = dp[l][r][1] = INF;
		}
	}

	dp[1][m][0] = dp[1][m][1] = 0;

	for(int len = m - 1; len >= 1; len--) {
		for(int l = 1; l + len - 1 <= m; l++) {
			int r = l + len - 1;

			if(!(l <= k && k <= r)) continue;

			if(l > 1) {
				ll d = x[l] - x[l - 1];

				dp[l][r][0] = min(
					dp[l][r][0],
					d + max(0LL, dp[l - 1][r][0] - e[l - 1])
				);

				d = x[r] - x[l - 1];

				dp[l][r][1] = min(
					dp[l][r][1],
					d + max(0LL, dp[l - 1][r][0] - e[l - 1])
				);
			}

			if(r < m) {
				ll d = x[r + 1] - x[l];

				dp[l][r][0] = min(
					dp[l][r][0],
					d + max(0LL, dp[l][r + 1][1] - e[r + 1])
				);

				d = x[r + 1] - x[r];

				dp[l][r][1] = min(
					dp[l][r][1],
					d + max(0LL, dp[l][r + 1][1] - e[r + 1])
				);
			}
		}
	}

	cout << min(dp[k][k][0], dp[k][k][1]);

	return 0;
}

二十一、逆向 DP 为什么要从大区间往小区间算？

例如我们想计算：

$dp[l][r]$

它需要知道：

$dp[l-1][r]$

或者：

$dp[l][r+1]$

这两个区间都比：

$[l,r]$

更大。

所以必须：

先算大区间，再算小区间。

因此区间长度 len 要从大到小枚举：

for(int len = m - 1; len >= 1; len--)

这就是这里“逆向”的另一层含义。

二十二、两种方法对比

方法	DP 中保存什么	时间复杂度	特点
二分 + 正向 DP	当前最多剩多少能量	$O(n^2\log C)$	比较直观，容易从“模拟机器人走路”理解
直接逆向 DP	当前最少需要多少能量	$O(n^2)$	更快、更巧，不需要二分

其中空间复杂度都是：

$O(n^2)$

二十三、最推荐记住的两个状态

如果以后再次遇到这种：

有资源、移动会消耗资源、到某些位置又能补充资源

的问题，可以尝试两种思考方式。

正着想

我已经走到这里了，最多还剩多少资源？

这道题就是：

$dp[l][r][0/1]=最大剩余能量$

反着想

为了完成后面的任务，我现在至少需要多少资源？

这道题就是：

$dp[l][r][0/1]=最少所需能量$

而逆向 DP 中最核心的式子只有一个：

$\boxed{d+\max(0,need-e)}$

其中：

$d$ ：走到下一块电池的距离
$e$ ：下一块电池能够补充的能量
$need$ ：捡完这块电池以后，完成剩余任务至少需要的能量

只要真正理解这个式子，第二种做法基本就理解了。

二十四、一句话总结整道题

先把起点也当成一个能量为 $0$ 的点，按坐标排序。

由于机器人向左右扩展时，下一块能遇到的电池一定是当前区间旁边的电池，所以：

已经回收的部分可以用一个区间 $[l,r]$ 表示。

于是：

正向 DP：求“走到这里最多还剩多少能量”，再配合二分答案；
逆向 DP：求“从这里开始至少需要多少能量”，直接得到最终答案。

如果只从代码长度和复杂度来看，更推荐掌握第二种逆向区间 DP。

有帮助，赞一个

去预览

0/2000

全部评论 2

wcqk
疑似 ABC471 C

3天前来自浙江
0
- cjdst
  回复
  wcqk
  不一样，这个有权值的
  
  3天前来自浙江
  0
- ༺ཌༀ`高家瑞是给′ༀད༻
  回复
  wcqk
  不要质疑这个人，这个人非常只牛逼，不要问我怎么知道的
  
  3天前来自广东
  1
༺ཌༀ`高家瑞是给′ༀད༻
吴老师nb

3天前来自广东
0