题解：P14044 [SDCPC 2019] Wandering Robot

题意：进行

n

次行动，每次向上下左右其中一个方向行动

1

个单位长度，重复

k

次，共行动

n\times k

次，问途中与原点的最大曼哈顿距离。

观察到一个性质，对于每一轮操作，即

n

次行动，我们的位移是一定的，于是途中最大曼哈顿距离一定在第一轮行动或最后一轮行动。

所以我们递推一轮操作，得到经过一轮操作后的位移，然后

\mathcal O(n)

地枚举首末轮操作这一步的曼哈顿距离，输出答案。

总时间复杂度

\mathcal O(n\times t)

。

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

Code：

CPP

#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;
}

题解：P14044 [SDCPC 2019] Wandering Robot

文章操作

相关推荐

评论

题解：P14044 [SDCPC 2019] Wandering Robot