题解：P10207 [JOI 2024 Final] 马拉松比赛 2
2huk
·
·
题解
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)\}
其中 $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;
}
```