SMMR-242: Dancing Zemo

#include <bits/stdc++.h>

using namespace std;
const int N = 1e4;
char str[N+10];
int dp[N+10][5][5];
int L;

int convert(char a){
    if(a == 'L') return 1;
    else if(a == 'R') return 2;
    else if(a == 'U') return 3;
    else if(a == 'D') return 4;
}

int DP(){

    for(int l = 1; l <= 4; l ++){
        for(int r = 1; r <= 4; r ++){
            dp[L][l][r] = (l == convert(str[L-1]) or r == convert(str[L-1]));
        }
    }

    for(int i = L-1; i >= 1; i --){
        for(int l = 1; l <= 4; l ++){
            for(int r = 1; r <= 4; r ++){
                if(l == r) continue;
                if(l == convert(str[i-1]) or r == convert(str[i-1])) dp[i][l][r] = 1 + dp[i+1][l][r];
                else {
                    if(l != convert(str[i-1])) dp[i][l][r] = max(dp[i][l][r], dp[i+1][l][convert(str[i-1])]);
                    if(r != convert(str[i-1])) dp[i][l][r] = max(dp[i][l][r], dp[i+1][convert(str[i-1])][r]);
                }
            }
        }
    }

    return dp[1][1][2];
}

void Setting(){
    for(int i = 0; i <= N; i ++){
        for(int l = 1; l <= 4; l ++){
            for(int r = 1; r <= 4; r ++){
                dp[i][l][r] = 0;
            }
        }
    }
}

int main(){

    int n;
    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        scanf("%s", str);
        L = strlen(str);
        printf("%d\n", DP());
        Setting();
    }

    return 0;
}