题解：AT_agc072_a [AGC072A] Rhythm Game
FLY_lai
·
·
题解
【题意】
给定 n,D。数轴上有 n 个点。第 i 个点在 x_i 出现，出现时段为 [t_i,t_i+D]。
现在你站在 0，可以按任意顺序访问这 n 个点，每访问完一个点都要回到 0。问是否能访问全部点。
# 【题解】
1. 原题目不好做，考虑增减条件怎么做，然后推广回原来的问题。
注意："相邻两个交换顺序" 对其他部分都没有影响，大概率能分析排序、贪心。
2. 如果推广遇到了困难，不要太早放弃。有的时候明明能 $O(n)$，题目却给的 $O(n^2)$，就是为了给你找方法解决困难的。
观察推广里的方案为什么不能直接回到原问题？能不能通过局部的微调解决？能不能通过一些有规律的、少量的决策就调整过来？能不能用 DP 做这些决策？
题目等价于 "有 $n$ 个任务，第 $i$ 个任务在 $t_i-x_i$ 时刻发布，需要 $2x_i$ 时间，截止时间 $t_i+x_i+D$"。
首先考虑没有发布时间怎么做。
考虑相邻两个任务 $i,j$，发现它们交换后对其他部分没有影响，考虑调整法。
记 $T$ 为做完 $i$ 之前任务的时间，$i,j$ 的要求是 $T\le t_i-x_i,T+2x_i\le t_j-x_j$，$j,i$ 的要求是 $T\le t_j-x_j,T+2x_j\le t_i-x_i$。
也就是 $\min(t_i-x_i,t_j-x_j-2x_i)$ 和 $\min(t_j-x_j,t_i-x_i-2x_j)$。这个东西越大越好。分类讨论。
1. 若 $t_i-x_i\le t_j-x_j-2x_i\iff t_i+x_i\le t_j-x_j$，因为 $t_i-x_i\ge t_i-x_i-2x_j$，$i,j$ 总是更优。
2. 否则就是要 $t_j-x_j-2x_i\ge t_i-x_i-2x_j\iff t_j+x_j\ge t_i+x_i$。
所以 $t_i+x_i\le t_j-x_j$ 时总是 $i$ 在前，$t_i+x_i\le t_j+x_j$ 时总是 $i$ 在前。总结一下就是按 $t+x$ 从小到大排序，依次访问即可。
好，此时已经解决了不带发布时间的问题，考虑怎么推广回去。
然后就发现这个推广非常难 …… 但是简单版只需要 $O(n\log n)$，这题允许 $O(n^2)$，这就给了我们克服困难的条件。
把任务按 $t+x$ 排序。我们想尽量按照这个顺序做任务，但可能想做的时候任务还没发布。仔细观察，排序后有这么一个规律：若 $i<j$，$j$ 已经做完了，那么 $i$ 一定已经发布！
证明：$j$ 是在 $t_j-x_j$ 时刻发布的，所以完成时刻至少是 $t_j+x_j\ge t_i+x_i\ge t_i-x_i$。
所以做任务的过程可以看作把任务分作若干个区间：每个区间先做了最后一个，此时前面的任务都发布了，再依次做过去，然后进入下一个区间。这个区间的决策很难想不到 DP。
于是我们容易得到这么一个 DP：$dp[i]$ 表示做完前 $i$ 个任务的最短时间，若无解则记作 $+\infty$。转移则枚举 $j<i$ 即可。因为还要额外一重循环判定 $[j+1,i]$ 合法，复杂度 $O(n^3)$。
还需要优化。一看这个循环判定就是要优化掉的。重新描述这个过程。令 $t_0=\max(dp[j],t_i-x_i)+2x_i$，也就是做完前 $j$ 个和第 $i$ 个的时刻。
- 若存在 $k\in [j+1,i-1]$ 使得 $t_0+2x_{j+1}+\cdots+2x_k>t_k+x_k+D$ 则不合法。
- 否则最后一个任务做完的时刻是 $t_0+2x_{j+1}+\cdots+2x_{i-1}$。
1 的条件可以表述为 $\max_{k = j+1, \dots, i-1} \{2X_{j+1} + \dots + 2X_k - (T_k + X_k)\}>D - t_0$。预处理前缀和、RMQ 等可以 $O(1)$ 求得最大值。
复杂度 $O(n^2)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f, N = 5005;
int n;
ll D;
ll t[N], x[N], L[N], R[N];
int p[N];
ll dp[N];
void slv() {
cin >> n >> D;
for (int i = 0; i < n; i++) {
cin >> t[i] >> x[i];
L[i] = t[i] - x[i];
R[i] = t[i] - x[i] + D;
x[i] *= 2;
}
for (int i = 0; i < n; i++)
p[i] = i;
sort(p, p + n, [](int i, int j){return L[i] < L[j];});
for (int i = 0; i <= n; i++)
dp[i] = inf;
dp[0] = 0;
for (int i = 0; i < n; i++) {
ll l = max(L[p[i]], dp[i]);
for (int j = i + 1; j <= n; j++) {
if (j > i + 1)
l = max(l, L[p[j - 1]]) + x[p[j - 1]];
if (l <= R[p[i]])
dp[j] = min(dp[j], l + x[p[i]]);
}
}
if (dp[n] == inf)
puts("No");
else
puts("Yes");
}
int main() {
int T;
cin >> T;
while (T--)
slv();
return 0;
}
```