题目链接：uva 1291 - Dance Dance Revolution
题目大意：有一台跳舞机，中间位置是0，然后从0的右边开始顺时针分别是1，2，3，4；从0到1，2，3，4要消耗2点体力；每个位置到斜角的消耗的体力为3点（例如1到2，4）；到对角消耗的体力4点（1到3）；原地不动消耗的体力为1；现在题目给出一个序列是要求踩的位置，两只脚的初始位置都在0，在跳得过程中不能两只脚同时放在一个位置上，求消耗的最小体力值。
解题思路：dp[i][l][r]表示在第i个目标位置，左脚在l上，右脚在r上的最小体力值。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1005;
const int M = 10;
const int INF = 0x3f3f3f3f;
int n, dp[N][M][M], val[M][M], p[N];
bool init() {
n = 1;
while (scanf("%d", &p[n]) == 1 && p[n]) n++;
n--;
for (int i = 1; i < 5; i++) {
val[i][0] = val[0][i] = 2;
val[i][i] = 1;
}
val[1][2] = val[1][4] = val[2][1] = val[2][3] = 3;
val[3][2] = val[3][4] = val[4][3] = val[4][1] = 3;
val[1][3] = val[3][1] = val[2][4] = val[4][2] = 4;
return n > 1;
}
int solve () {
memset(dp, INF, sizeof(dp));
dp[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
int u = p[i];
for (int l = 0; l < 5; l++) {
for (int r = 0; r < 5; r++) {
if (u != r)
dp[i][u][r] = min(dp[i][u][r], dp[i-1][l][r] + val[l][u]);
if (u != l)
dp[i][l][u] = min(dp[i][l][u], dp[i-1][l][r] + val[r][u]);
}
}
}
int ans = INF;
for (int i = 1; i < 5; i++) {
for (int j = 1; j < 5; j++) ans = min(ans, dp[n][i][j]);
}
return ans;
}
int main () {
while (init()) {
printf("%d\n", solve());
}
return 0;
}