『算法-ACM 竞赛-真题』ACM-ICPC 2019 山东省省赛 C Wandering Robot

这个题额，我觉的是一道水题，思维题，需要考虑的情况比较多，题意一个机器人给一条指令，循环 n 遍，问此过程中离原点最远距离。
考虑最远距离可能出现的的情况。
每次循环之后距离至少为 0； 1.假设他每一次循环都能回到原点，最远值肯定出现在第一重循环。 2.假设每次循环结束后所移动距离都小于，在某次循环中向某个方向移动的距离。
因为每次循环都会朝某一个方向但是，移动的量过于小，不如一个方向，此时，应考虑 N 次循环后的的位置，与第一次循环 之后的大小。
比较难理解上图：


综上所述，只用考虑第一次循环的最大值，跟最后一次循环的最大值谁大即可。
移动是有方向的，对于 X，Y 都有正负。

#include<iostream>
using namespace std;
long long jdz(long long int a);
const int maxn=1e5+5;
int main()
{
    char ob[maxn];
    int t;
    long long dx,dy,max;
    cin>>t;
    while(t--)
    {
        int n,k;
        dx=dy=max=0;
        cin>>n>>k;
        for(int i=0; i<n; i++)
        {
            cin>>ob[i];
            if(ob[i]=='U') dy++;
            if(ob[i]=='D') dy--;
            if(ob[i]=='L') dx--;
            if(ob[i]=='R') dx++;
            if((jdz(dx)+jdz(dy))>max) max=jdz(dx)+jdz(dy);
            //比赛时，紧张用了好几遍sqrt()难受；
            //编译器出了问题，abs()不能用，蛋疼；
        }
        dx=(k-1)*dx;
        dy=(k-1)*dy;
        for(int i=0; i<n; i++)
        {
            if(ob[i]=='U') dy++;
            if(ob[i]=='D') dy--;
            if(ob[i]=='L') dx--;
            if(ob[i]=='R') dx++;
            if((jdz(dx)+jdz(dy))>max) max=jdz(dx)+jdz(dy);
        }
        cout<<max<<endl;
    }
}
long long jdz(long long int a)
{
    if(a>0) return a;
    else return -a;
}