题解：P14044 [SDCPC 2019] Wandering Robot

· · 题解

思路

仅需计算第一次和最后一次。

最后一次是因为每次会对上一次产生一个相对偏移，最后一次是偏移最远的。

第一次是因为这个数据：

1
17 2
LLLLLLLDRRRRRRRRU

答案是 8（在第一次运行到 D），但是算最后一次，就是 7。

原因：第一次可能存在一个点，与后续偏移方向相反，它是答案，但是不会被计算。中间的可以证明不存在这样的。

代码

需要开 long long！！！！

#include <bits/stdc++.h>
using namespace std;
#define int long long
void mian()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int x = 0, y = 0;
    int ans = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (s[i - 1] == 'U') y ++;
        else if (s[i - 1] == 'D') y --;
        else if (s[i - 1] == 'L') x --;
        else if (s[i - 1]) x ++;
        ans = max (ans, abs (x) + abs(y));
    }
    x = x * (k - 1), y = y * (k - 1);
    for (int i = 1; i <= n; i ++)
    {
        if (s[i - 1] == 'U') y ++;
        else if (s[i - 1] == 'D') y --;
        else if (s[i - 1] == 'L') x --;
        else if (s[i - 1]) x ++;
        ans = max (ans, abs (x) + abs(y));
    }
    cout << ans << endl;
}
signed main(){
    int T;
    cin >> T;
    while (T --) mian();
}