题意：有一台跳舞机，中间是0。上左下右分别代表1 2 3 4，初始状态人站在中间。两仅仅脚都踏在0上，然后给出一段序列以0为结束，要按顺序踩出来，从0踏到四个方向须要消耗2点能量，从一个方向到相邻的方向消耗3点能量，从一个方向到对面方向消耗4点能量，在一个方向原地再踩一次消耗1点能量，问把全部序列踩完最少消耗多少能量。
题解：f[i][j][k]表示踩前i步左脚在方向j上右脚在方向k上最少消耗多少能量。那么就要分两种情况讨论：
（1）f[i][j][a[i]] 的前一步是f[i - 1][a[i - 1]][k]或f[i - 1][k][a[i - 1]]。这两种情况再加上这一步移动消耗能量取较小值。
（2）f[i][a[i]][j]和上面相似
结果在f[n][a[n]][k]和f[n][k][a[n]]中取最小值就是解。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100000;
int n, a[N], f[N][5][5];
int Count(int x, int y) {
if (x == 0)
return 2;
int temp = fabs(x - y);
if (temp == 0)
return 1;
if (temp % 2)
return 3;
return 4;
}
int main() {
while (1) {
n = 1;
scanf("%d", &a[n]);
if (a[n] == 0)
break;
while (a[n]) {
n++;
scanf("%d", &a[n]);
}
n--;
memset(f, INF, sizeof(f));
f[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 4; j++) {
if (j != a[i]) {
if (a[i - 1] == j) {
for (int k = 0; k <= 4; k++)
if (k != a[i - 1] || i == 1) {
f[i][j][a[i]] = min(f[i][j][a[i]], f[i - 1][j][k] + Count(k, a[i]));
f[i][a[i]][j] = min(f[i][a[i]][j], f[i - 1][k][j] + Count(k, a[i]));
}
}
else {
f[i][j][a[i]] = min(f[i][j][a[i]], f[i - 1][j][a[i - 1]] + Count(a[i - 1], a[i]));
f[i][a[i]][j] = min(f[i][a[i]][j], f[i - 1][a[i - 1]][j] + Count(a[i - 1], a[i]));
}
}
}
}
int res = INF;
for (int i = 1; i <= 4; i++) {
res = min(res, f[n][i][a[n]]);
res = min(res, f[n][a[n]][i]);
}
printf("%d\n", res);
}
return 0;
}