题解：P14044 [SDCPC 2019] Wandering Robot

· · 题解

题意：进行 n 次行动，每次向上下左右其中一个方向行动 1 个单位长度，重复 k 次，共行动 n\times k 次，问途中与原点的最大曼哈顿距离。

观察到一个性质，对于每一轮操作，即 n 次行动，我们的位移是一定的，于是途中最大曼哈顿距离一定在第一轮行动或最后一轮行动。

所以我们递推一轮操作，得到经过一轮操作后的位移，然后 \mathcal O(n) 地枚举首末轮操作这一步的曼哈顿距离，输出答案。

总时间复杂度 \mathcal O(n\times t)。

代码可读性我个人认为挺高的，光看代码应该也能懂

Code：

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;
using ll = long long;

constexpr int N = 1e5 + 5;
int T, n, k;
char msg[N];
pair <ll, ll> pos[N];

constexpr int dx[4] = {0, 0, -1, 1};
constexpr int dy[4] = {1, -1, 0, 0};

inline void move (ll &x, ll &y, char c) {
    int it;
    if (c == 'U') it = 0;
    if (c == 'D') it = 1;
    if (c == 'L') it = 2;
    if (c == 'R') it = 3;
    x += dx[it], y += dy[it];
}

inline ll dist (ll x, ll y) {
    return (x > 0ll ? x : -x) + (y > 0ll ? y : -y);
}

int main () {
    cin >> T;
    while (T --) {
        cin >> n >> k;
        ll x = 0, y = 0, fnl = 0;
        for (int i = 1; i <= n; ++ i) {
            cin >> msg[i];
            move(x, y, msg[i]);
            pos[i] = {x, y};
        }
        k --;
        pos[0] = {0, 0};
        for (int i = 0; i <= n; ++ i) {
            fnl = max(fnl, dist(x * k + pos[i].first, y * k + pos[i].second));
            fnl = max(fnl, dist(pos[i].first, pos[i].second));
        }
        cout << fnl << '\n';
    }
    return 0;
}