HDU 5074 Hatsune Miku：動態規劃優化音符序列

問題描述

創作長度為 n 的歌曲，每位置選擇 m 種音符之一。連續兩音符 (a,b) 產生美感分 score(a,b)。部分位置固定音符（正數），其餘可任意選（-1）。最大化總美感。n ≤ 100, m ≤ 50, T ≤ 10。

動態規劃模型

• 狀態：dp[i][j] 表示前 i 個位置，第 i 位選音符 j 的最大美感。
• 轉移：dp[i][j] = max_k { dp[i-1][k] + score(k, j) }，受固定音符約束。
• 初始：dp[1][j] = 0（無前驅）。
• 答案：最後位置固定則取對應值，否則取最大值。

條件分支處理

根據第 i、i-1 位是否固定，分四種情況轉移，避免無效循環：

• 兩者均固定：單一轉移。
• i 固定，i-1 不固定：枚舉 k 更新 dp[i][fixed]。
• i 不固定，i-1 固定：枚舉 j 更新 dp[i][j]。
• 兩者均不固定：雙重循環 k,j 全更新。

核心代碼

for (int i = 2; i <= n; i++) {
    if (b[i] != -1) { // 當前固定
        if (b[i-1] == -1) {
            for (int j = 1; j <= m; j++)
                dp[i][b[i]] = max(dp[i][b[i]], dp[i-1][j] + a[j][b[i]]);
        } else
            dp[i][b[i]] = dp[i-1][b[i-1]] + a[b[i-1]][b[i]];
    } else { // 當前不固定
        if (b[i-1] == -1) {
            for (int j = 1; j <= m; j++)
                for (int k = 1; k <= m; k++)
                    dp[i][j] = max(dp[i][j], dp[i-1][k] + a[k][j]);
        } else {
            for (int j = 1; j <= m; j++)
                dp[i][j] = max(dp[i][j], dp[i-1][b[i-1]] + a[b[i-1]][j]);
        }
    }
}

複雜度

• 時間：O(n * m²) 最壞情況，n=100, m=50 约 2.5e5 操作/用例，極快。
• 空間：O(n * m)。

總結

本題是典型的線性 DP，狀態定義清晰，轉移方程直觀。關鍵在於仔細處理固定/自由位置的條件分支，代碼雖長但邏輯清晰，屬於「水 DP」範疇，適合鍛鍊 DP 建模與分支處理能力。