学步园

一开始偷懒没读原题，根据白书里的描述似懂非懂的做了，WA了还纳闷半天。最好还是先读原题啊，有些看似无用的句子会给很多有用的信息

每个决策要受到几个因素的影响：1、当前时间  2、左脚位置   3、右脚位置  4、上一次动了哪只脚

前三个因素比较intuitive。第4个因素来自题目中的叙述：如果这次动的脚和上次的不同，则只消耗1个能量。如果这次和上次动的是同一只脚，则分三种情况，分别对应3、5、7个能量。所以上次动的脚也应该包含在状态中。

除了状态的设计，还要看一下哪些情况下状态不能转移，要注意细节。

Run Time: 0.032s

#define UVa  "LT9-18.10618.cpp"		//Tango Tango Insurrection
char fileIn[30] = UVa, fileOut[30] = UVa;

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

//Global Variables. Reset upon Each Case!
const int maxn = 70 + 5, INF = 99999999;
const int DIRUP = 0, DIRRIGHT = 1, DIRDOWN = 2, DIRLEFT = 3;
const int FTLEFT = 1, FTRIGHT = 2, FTSTILL = 0;
int DIR[300];
char FOOT[3];
char line[maxn];
int s[maxn];
int n;
int d[maxn][4][4][3];
int act[maxn][4][4][3];
/////

int non_still_energy(int p, int tp) {
    if(abs(p-tp) == 2) return 7;
    else if(p == tp) return 3;
    return 5;
}

int energy(int u, int l, int r, int tl, int tr, int move, int prev) {
    if(move == FTSTILL)
        return 0;
    if(prev != move) return 1;
    else if(move == FTLEFT)
        return non_still_energy(l, tl);
    else
        return non_still_energy(r, tr);
}

void update(int& ans, int& action, int u, int l, int r, int tl, int tr, int move, int prev) {
    if(tl != l || tr != r) {
        if(tl == r || tr == l) return;
        if(tl == DIRRIGHT && tr == DIRLEFT) return;
        if(l == DIRRIGHT && move != FTLEFT) return;
        if(r == DIRLEFT && move != FTRIGHT) return;
    }
    int& ans_v = d[u+1][tl][tr][move];
    int e = energy(u, l, r, tl, tr, move, prev);
    if(ans_v + e < ans) {
        ans = ans_v + e;
        action = 100*tl + 10*tr + move;
    }
}

void print_ans() {
    int l = DIRLEFT, r = DIRRIGHT, m = 0;

    for(int u = 0; u < n; u ++) {
        int action = act[u][l][r][m];
        l = action/100;
        r = (action/10)%10;
        m = action%10;
        printf("%c", FOOT[m]);
    }
    printf("\n");
}

int dp() {
    for(int u = n-1; u >= 0; u --) {          //notice the boundary
        for(int l = 0; l < 4; l ++) {
            for(int r = 0; r < 4; r ++) {
                for(int m = 0; m < 3; m ++) {
                    int &ans = d[u][l][r][m], &action = act[u][l][r][m];
                    ans = INF;
                    if(s[u] == -1) {     //empty note
                        update(ans, action, u, l, r, l, r, FTSTILL, m);
                        for(int i = 0; i < 4; i ++) {
                            update(ans, action, u, l, r, i, r, FTLEFT, m);
                            update(ans, action, u, l, r, l, i, FTRIGHT, m);
                        }
                    }
                    else {
                        update(ans, action, u, l, r, s[u], r, FTLEFT, m);
                        update(ans, action, u, l, r, l, s[u], FTRIGHT, m);
                    }
                }
            }
        }
    }
    print_ans();
}


int main() {
    DIR['U'] = 0, DIR['R'] = 1, DIR['D'] = 2, DIR['L'] = 3, DIR['.'] = -1;
    FOOT[FTLEFT] = 'L', FOOT[FTRIGHT] = 'R', FOOT[FTSTILL] = '.';
    while(scanf("%s", line) && line[0] != '#') {
        n = strlen(line);
        for(int i = 0; i < n; i ++) s[i] = DIR[line[i]];

        memset(d, 0, sizeof(d));
        memset(act, -1, sizeof(-1));
        dp();
    }
    return 0;
}