题解：P10207 [JOI 2024 Final] 马拉松比赛 2

MX-C 8.16 模拟赛 T4。

对楼上大佬的题解做的一些详细解释。

## 题意

一条数轴上放了 $n$ 个球，第 $i$ 个球放在了位置 $x_i$，一个位置可能有多个球。

你需要从起点 $s$ 出发，捡起所有 $n$ 个球（一个球捡起了就不能放下了），回到终点 $t$。如果你能在规定时间 $T$ 内完成，则算你成功。

已知：拿起 $1$ 个球需要 $1$ 单位时间；带着 $x$ 个球移动 $1$ 个单位距离需要 $x + 1$ 单位时间。

给定 $n,l,x_i$，你需要回答 $q$ 个询问，每个询问给定 $s,t,T$，你需要回答能不能成功。

所有数都 $\le 5 \times 10^5$。

## 做法

显然第一步是将球按照坐标排序。

我们考虑如果在 $t$ 的某侧有两个球，那么最优策略一定是选捡那个远的再捡近的。这是因为如果先捡近的你会抱着这个球跑一个来回。

所以对于 $t$ 的某侧（左侧或右侧）而言，一定是先捡最远的，再捡第二远的，以此类推。所以我们捡的第一个球一定是第一个或第 $n$ 个，这是因为我们将球按坐标排序了。

考虑最朴素的区间 DP。设 $f(l, r, 0/1)$ 表示我们已经捡了 $[1, l-1]$ 和 $[r+1, n]$ 这些球，且现在我们正位于第 $l/r$ 个球的位置，所需要的最小时间。这样设状态的问题是没法设置边界，因此我们再引入一个与 $f$ 意义相同的 $g$，其中 $f$ 表示起点是第一个球，$g$ 表示起点是第 $n$ 个球。

显然边界 $f(1,n,0) = 0,g(1,n,1)=0$。转移枚举一下最后一个捡的球是 $l - 1$ 还是 $r + 1$：

$$
f(l,r,0) = \min \{f(l-1,r,0) + (cnt+1)\times (x_l - x_{l - 1}), f(l, r+1, 1) + (cnt+1)\times (x_{r+1}-x_l)\} \\
f(l,r,1) = \min \{f(l-1,r,0)+(cnt+1)\times(x_r - x_{l-1}), f(l,r+1,1)+(cnt+1)\times(x_{r+1}-x_r)\}
$$

$g$ 的转移**一模一样**。

其中 $cnt = (l-1) + (n-r)$，表示 $[1,l-1] \cup [r+1,n]$ 的大小，即当前在手上的球的数量。

考虑计算答案。对于 $t$ 的一侧而言，因为我们按照球到 $t$ 的距离从大到小取球，所以最后一个球一定距离 $t$ 最近。分别求出这两侧的这两个最近的球 $p_1,p_2$。那么我们可以枚举第一个取的球（第 $1$ 个或第 $n$ 个），以及最后一个取的球（第 $p_1$ 个或第 $p_2$ 个），即：

$$
\min \{|s-x_1| + f(p,p,0) + (n + 1) \times |x_p-t|, |s-x_n| + f(p,p,0) + (n+1) \times |x_p - t|\}
$$

其中 $p \in \{p_1,p_2\}$，我们可以枚举。

复杂度？$n^2$ 过五十万你搞笑呢？

令 $S$ 表示将球的坐标去重后的数量。**注意到**在最坏情况下，如果我们在第一米捡第一个球，第二米捡第二个球，以此类推，那么总答案为 $2+3+\dots+(S+1) = \mathcal O(S^2)$。而 $t \le 5 \times 10^5$ 远小于这个数，所以当 $S$ 大于某个阈值后全输出 $\texttt{No}$ 即可。这个阈值是 $10^3$。

那么区间 DP 的状态数优化到了 $10^3 \times 10^3 \times 2$。这是被允许的。

去重后实现较为复杂。一个记忆化搜索的实现如下：

```cpp
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10, INF = 1e9;

int n, L, x[N];
int s[N];
int f[1010][1010][2];
int g[1010][1010][2];

int dp0(int l, int r, bool flg) {
	if (l == 1 && r == n) return flg ? INF : 0;
	if (~f[l][r][flg]) return f[l][r][flg];
	int res = 1e9;
	
	int sum = 1 + (x[l] ? s[x[l] - 1] : 0) + s[L] - s[x[r]];
	
	if (!flg) {
		if (l > 1) res = min(res, dp0(l - 1, r, 0) + sum * (x[l] - x[l - 1]));
		if (r < n) res = min(res, dp0(l, r + 1, 1) + sum * (x[r + 1] - x[l]));
	}
	else {
		if (l > 1) res = min(res, dp0(l - 1, r, 0) + sum * (x[r] - x[l - 1]));
		if (r < n) res = min(res, dp0(l, r + 1, 1) + sum * (x[r + 1] - x[r]));
	}
	
	return f[l][r][flg] = res;
}

int dp1(int l, int r, bool flg) {
	if (l == 1 && r == n) return !flg ? INF : 0;
	if (~g[l][r][flg]) return g[l][r][flg];
	int res = 1e9;
	
	int sum = 1 + (x[l] ? s[x[l] - 1] : 0) + s[L] - s[x[r]];
	
	if (!flg) {
		if (l > 1) res = min(res, dp1(l - 1, r, 0) + sum * (x[l] - x[l - 1]));
		if (r < n) res = min(res, dp1(l, r + 1, 1) + sum * (x[r + 1] - x[l]));
	}
	else {
		if (l > 1) res = min(res, dp1(l - 1, r, 0) + sum * (x[r] - x[l - 1]));
		if (r < n) res = min(res, dp1(l, r + 1, 1) + sum * (x[r + 1] - x[r]));
	}
	
	return g[l][r][flg] = res;
}

signed main() {
	cin >> n >> L;
	
	int backup = n;
	
	for (int i = 1; i <= n; ++ i ) {
		cin >> x[i];
		s[x[i]] ++ ;
	}
	
	for (int i = 1; i <= L; ++ i ) {
		s[i] += s[i - 1];
	}
	
	sort(x + 1, x + n + 1);
	n = unique(x + 1, x + n + 1) - x - 1;
	
	memset(f, -1, sizeof f);
	memset(g, -1, sizeof g);
	
	int q;
	cin >> q;
	
	while (q -- ) {
		if (n > 1e3) {
			puts("No");
			continue;
		}
		
		int s, t, jp;
		cin >> s >> t >> jp;
		
		int res = 1e9;
		
		if (x[n] >= t) {
			int p = lower_bound(x + 1, x + n + 1, t) - x;
			res = min(res, abs(s - x[1]) + dp0(p, p, 0) + (backup + 1) * abs(x[p] - t));
			res = min(res, abs(s - x[n]) + dp1(p, p, 0) + (backup + 1) * abs(x[p] - t));
		}
		
		if (x[1] < t) {
			int p = lower_bound(x + 1, x + n + 1, t) - x - 1;
			res = min(res, abs(s - x[1]) + dp0(p, p, 0) + (backup + 1) * abs(x[p] - t));
			res = min(res, abs(s - x[n]) + dp1(p, p, 0) + (backup + 1) * abs(x[p] - t));
		}
		
		res += backup;
		
		puts(res <= jp ? "Yes" : "No");
	}
	
	return 0;
}
```

正在渲染内容...