UVA 1291 Dance Dance Revolution：雙腳動態規劃

問題建模

• 舞臺有 5 個位置：0（中心），1（上），2（左），3（下），4（右）。
• 雙腳初始均在 0。需按序列 a[1..n] 踩踏。
• 移動能耗：
   0→任意方向 = 2
   同方向 = 1
   相鄰方向（1↔2, 2↔3, 3↔4, 4↔1）= 3
   相反方向（1↔3, 2↔4）= 4

狀態定義

dp[i][j]：已完成前 i 步，其中一腳停留在 a[i]（剛踩完的位置），另一腳在 j（0..4）的最小總能耗。
因為剛踩完的那隻腳位置固定為 a[i]，另一腳位置 j 即為自由狀態。

轉移方程

設 cost(x, y) 為從 x 移動到 y 的能耗。

dp[i+1][j]     = min(dp[i+1][j],     dp[i][j] + cost(a[i], a[i+1]));      // 動已在 a[i] 的腳
dp[i+1][a[i]]  = min(dp[i+1][a[i]],  dp[i][j] + cost(j, a[i+1]));          // 動另一隻腳

初始化與邊界

• dp[1][0] = cost(0, a[1])（第一步必須從中心出發）。
• 其餘 INF。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int a[100010];
int dp[100010][5];

int cost(int from, int to) {
    if (from == 0) return 2;
    if (from == to) return 1;
    int d = abs(from - to);
    if (d == 1 || d == 3) return 3; // 相鄰
    return 4; // 相反
}

int main() {
    while (true) {
        int n = 0;
        while (scanf("%d", &a[++n]) && a[n]); // 以 0 結束
        if (n == 1) break; // 只有終止符 0
        --n;
        for (int i = 0; i <= n; ++i)
            fill(dp[i], dp[i]+5, INF);
        dp[1][0] = cost(0, a[1]);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= 4; ++j) if (dp[i][j] < INF) {
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + cost(a[i], a[i+1]));
                dp[i+1][a[i]] = min(dp[i+1][a[i]], dp[i][j] + cost(j, a[i+1]));
            }
        }
        int ans = INF;
        for (int j = 0; j <= 4; ++j) ans = min(ans, dp[n][j]);
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

• 狀態數：n × 5
• 轉移：O(1)
• 總時間 O(n)，空間 O(n)（可滾動數組優化至 O(1)）。