uva 1291(dp)[通俗易懂]

全栈程序员-站长 • 2022年1月30日下午9:00 • 未分类 • 阅读 37

大家好，又见面了，我是全栈君。

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