这里记 为 两个点在三维空间中的曼哈顿距离。
先特判掉一些 corner case：
- 是容易解决的。
- 如果有一个传送器 满足 ，则答案为 。
- 否则，若存在两个传送器满足其中一个距离 更近，另外一个距离 更近，则建系一下可知此时必然存在一组答案为 的构造。
处理完上面的 corner 后必然可以通过交换 使得对每个传送器 都满足 。考虑 dp，设 表示经过 次传送后所有可达位置到 的最大距离是多少。初始条件为 ，转移可以直接枚举下一个移动的位置，即 。然后考虑到可达区域在三维空间中是一个连续的光滑部分，因此若可以移动到的最远距离为 ，则一定可以移动到 中的任意实数距离，也就是说只要 就可以在第 次传送到达 点。
直接暴力 dp 时间复杂度肯定爆炸了，考虑经典套路拆曼哈顿距离，。因为三个 的不同取值只有 种，因此考虑记 。额外记 后代入可以得到转移式 ，这可以看作是一个 的 矩阵乘法的形式。再预处理出 ，则判定 对应的状态能否在第 次传送中到达终点只需要判定 是否成立即可。具体实现可以对 矩阵作倍增处理，时间复杂度为 ，其中 是坐标的范围， 是矩阵的边长，在本题中取 。
描述的可能不太清楚，建议对着题解代码理解。我还是不懂这个题为什么单个测试点时间限制 ，我的代码跑了 就跑过了。
namespace lowspeed_song {
mt19937_64 mt(time(0));
inline void init() {
}
struct Point { int x, y, z; } a[N];
inline int dist(Point a, Point b) {
return abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z);
}
const i128 inf = (i128)1 << 120;
i128 e[45][8][8], g[8], h[8], tmp[8], d[160][8];
inline void in(Point &p) { cin >> p.x >> p.y >> p.z; }
inline void sol([[maybe_unused]]int __testcase_id, [[maybe_unused]]int __testcase_sum) {
int n; cin >> n;
Point p, q; in(p), in(q);
for (int i = 0; i < n; ++i) in(a[i]);
cout << "Case #" << __testcase_id << ": ";
int o1 = 0, o2 = 0, o3 = 0;
for (int i = 0; i < n; ++i) {
int d1 = dist(p, a[i]), d2 = dist(q, a[i]);
o1 |= (d1 < d2), o2 |= (d1 > d2), o3 |= (d1 == d2);
} if (o3) { cout << 1 << '\n'; return; }
if (n == 1) { cout << "IMPOSSIBLE\n"; return; }
if (o1 && o2) { cout << 2 << '\n'; return; }
if (o2) swap(p, q);
for (int i = 0; i < 8; ++i) g[i] = h[i] = -inf;
for (int i = 0; i < n; ++i) for (int j = 0; j < 8; ++j) {
d[i][j] = 0;
d[i][j] += (j & 1) ? a[i].x : -a[i].x;
d[i][j] += (j & 2) ? a[i].y : -a[i].y;
d[i][j] += (j & 4) ? a[i].z : -a[i].z;
g[j] = max(g[j], (i128)dist(p, a[i]) - d[i][j]);
h[j] = max(h[j], (i128)d[i][j] - dist(q, a[i]));
} auto chk = [&](i128 *f) {
for (int i = 0; i < 8; ++i) if (f[i] + h[i] >= 0) return 1;
return 0;
}; if (chk(g)) { cout << 2 << '\n'; return; }
for (int i = 0; i < 8; ++i) for (int j = 0; j < 8; ++j) {
e[0][i][j] = -inf; for (int k = 0; k < n; ++k)
e[0][i][j] = max(e[0][i][j], d[k][j] - d[k][i]);
} for (int k = 1; k < 45; ++k) for (int i = 0; i < 8; ++i) for (int j = 0; j < 8; ++j) {
e[k][i][j] = -inf; for (int p = 0; p < 8; ++p)
e[k][i][j] = max(e[k][i][j], e[k - 1][i][p] + e[k - 1][p][j]);
} int res = 0; for (int i = 44; ~i; --i) {
for (int j = 0; j < 8; ++j) {
tmp[j] = -inf;
for (int k = 0; k < 8; ++k) tmp[j] = max(tmp[j], g[k] + e[i][j][k]);
} if (!chk(tmp)) copy(tmp, tmp + 8, g), res |= (1ll << i);
} cout << res + 3 << '\n';
}
} // namespace lowspeed_song
喜欢的话，留下你的评论吧～