例题 9-18 跳舞机（Tango Tango Insurrection，UVa 10618）

本文主要是介绍例题 9-18 跳舞机（Tango Tango Insurrection，UVa 10618），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-10618
分类：多维DP
备注：多阶段决策问题

主要还是参考了别人的解法，但理解起来很容易。

#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;
const int INF = 0x3f3f3f3f;
// 0-up 1-left 2-right 3-down
// 0:neither 1:left 2:right
char inp[100];
int n, d[100][4][4][3], rec[100][4][4][3];inline int cost(int pp, int np, int s, int ne) {if (ne != s) return 1;else {if (pp == np) return 3;else if (pp + np == 3) return 7;else return 5;}
}// 如果没发生位置的改变, 则tag为1.
int dp(int i, int a, int b, int s, int tag) {if ((a == 2 && b == 1) || a == b) return INF;if (((b == 1 && s == 1) || (a == 2 && s == 2)) && !tag) return INF;if (i == n) return 0;if (d[i][a][b][s] != -1) return d[i][a][b][s];int& res = d[i][a][b][s];res = INF;if (inp[i] == '.') { // 没有特别要求for (int op = 0; op < 4; op++) {if (dp(i + 1, op, b, 1, op == a) + cost(a, op, s, 1) < res) {res = dp(i + 1, op, b, 1, op == a) + cost(a, op, s, 1);rec[i][a][b][s] = 4 + op;}if (dp(i + 1, a, op, 2, op == b) + cost(b, op, s, 2) < res) {res = dp(i + 1, a, op, 2, op == b) + cost(b, op, s, 2);rec[i][a][b][s] = 8 + op;}}if (dp(i + 1, a, b, 0, 1) < res) {res = dp(i + 1, a, b, 0, 1);rec[i][a][b][s] = 0;}} else { // 必须踩箭头if (dp(i + 1, inp[i], b, 1, inp[i] == a) + cost(a, inp[i], s, 1) < res) {res = dp(i + 1, inp[i], b, 1, inp[i] == a) + cost(a, inp[i], s, 1);rec[i][a][b][s] = 4 + inp[i];}if (dp(i + 1, a, inp[i], 2, inp[i] == b) + cost(b, inp[i], s, 2) < res) {res = dp(i + 1, a, inp[i], 2, inp[i] == b) + cost(b, inp[i], s, 2);rec[i][a][b][s] = 8 + inp[i];}}return res;
}int main(void) {
//    freopen("in.txt", "r", stdin);while (~scanf("%s", inp) && inp[0] != '#') {n = strlen(inp);for (int i = 0; i < n; i++) {if (inp[i] == 'U') inp[i] = 0;if (inp[i] == 'L') inp[i] = 1;if (inp[i] == 'R') inp[i] = 2;if (inp[i] == 'D') inp[i] = 3;}memset(d, -1, sizeof(d));dp(0, 1, 2, 0, 1);int a = 1, b = 2, s = 0;for (int i = 0; i < n; i++) {int foot = rec[i][a][b][s] / 4;int npos = rec[i][a][b][s] % 4;if (foot == 0) printf(".");else if (foot == 1) printf("L");else printf("R");s = foot;if (foot == 1) a = npos;else if (foot == 2) b = npos;}printf("\n");}return 0;
}