题意：有一台跳舞机，中间是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;

}