NOJ 1859 越野賽：三維 DP 最小化換車策略總時間

NOJ 1859「越野賽」：N 段賽道，M 輛車，最多換 Q 次車。車 i 在段 j 耗時 t[i][j]。起始選車不算換車。求最小總時間。本文解析三維 DP：dp[段][換車次][當前車]。

狀態定義

dp[i][j][k] = 前 i 段，換了 j 次車，第 i 段用車 k 的最小時間。

狀態轉移

第 i 段用車 k，兩種來源：

1. 不換車：第 i-1 段也用車 k，換車次數不變。
   dp[i][j][k] = dp[i-1][j][k] + t[k][i]
2. 換車：第 i-1 段用車 x (x ≠ k)，換車次數 j-1。
   dp[i][j][k] = min_{x≠k} dp[i-1][j-1][x] + t[k][i]

合併：dp[i][j][k] = min(dp[i-1][j][k], min_{x≠k} dp[i-1][j-1][x]) + t[k][i]

初始化

• dp[1][0][k] = t[k][1]：第一段任選車，換車次數 0。
• dp[i][0][k] = dp[i-1][0][k] + t[k][i]：全程不換車，固定用車 k。
• 其餘 INF。

優化：預計算 min 值

內層 min_{x≠k} 可預計算：

• 對每個 (i-1, j-1)，找出最小值 min1 及其車 argmin，次小值 min2。
• 則 min_{x≠k} = (k == argmin) ? min2 : min1。
• 將轉移從 O(M) 降為 O(1)。

完整代碼（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 10010;
const int MAXM = 15;
const int MAXQ = 105;
const int INF = 1e9;

int t[MAXM][MAXN]; // t[車][段]
int dp[MAXN][MAXQ][MAXM];

int main() {
    int N, M, Q;
    while (scanf("%d%d%d", &N, &M, &Q) == 3) {
        for (int i = 1; i <= M; ++i)
            for (int j = 1; j <= N; ++j)
                scanf("%d", &t[i][j]);

        // 初始化
        for (int i = 0; i <= N; ++i)
            for (int j = 0; j <= Q; ++j)
                for (int k = 1; k <= M; ++k)
                    dp[i][j][k] = INF;

        // 第一段
        for (int k = 1; k <= M; ++k) dp[1][0][k] = t[k][1];
        // 不換車前綴
        for (int k = 1; k <= M; ++k)
            for (int i = 2; i <= N; ++i)
                dp[i][0][k] = dp[i-1][0][k] + t[k][i];

        // DP
        for (int i = 2; i <= N; ++i) {
            for (int j = 1; j <= Q && j < i; ++j) {
                // 預計算 dp[i-1][j-1] 的最小和次小
                int min1 = INF, min2 = INF, argmin = -1;
                for (int k = 1; k <= M; ++k) {
                    if (dp[i-1][j-1][k] < min1) {
                        min2 = min1;
                        min1 = dp[i-1][j-1][k];
                        argmin = k;
                    } else if (dp[i-1][j-1][k] < min2) {
                        min2 = dp[i-1][j-1][k];
                    }
                }
                for (int k = 1; k <= M; ++k) {
                    int best = dp[i-1][j][k]; // 不換車
                    int fromOther = (k == argmin) ? min2 : min1; // 換車
                    best = min(best, fromOther);
                    dp[i][j][k] = best + t[k][i];
                }
            }
        }

        // 答案
        int ans = INF;
        for (int j = 0; j <= Q; ++j)
            for (int k = 1; k <= M; ++k)
                ans = min(ans, dp[N][j][k]);
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

• 狀態數：N × Q × M ≤ 10000 × 100 × 10 = 10⁷。
• 優化後轉移 O(1)，總時間 ~10⁷ 操作，1 秒內可過。
• 空間：10⁷ × 4 bytes ≈ 40 MB，接近限制。可滾動數組優化至 O(Q×M)。

滾動數組優化空間

只需 dp[2][MAXQ][MAXM]，按 i%2 交替。

總結

本題是「分段決策 + 有限切換次數 + 多選項」的經典三維 DP。關鍵優化：

1. 預計算 min/次小 將 O(M) 轉移降為 O(1)。
2. 滾動數組 將空間從 O(NQM) 降為 O(QM)。
3. 初始化細節：第一段不算換車，dp[1][0][*] 直接賦值。

此模式適用於「序列分段、每段選擇狀態、切換成本/次數受限」問題。