UVa 690 Pipeline Scheduling：DFS + 剪枝求最短調度長度

問題模型

10 個任務，5 條流水線。每任務在各流水線上佔用特定時間（'X' 表示佔用）。任務可錯開啟動，求完成所有任務的最短總時間。

狀態表示與剪枝

• 用 5 個整數位掩碼 w[5] 表示單個任務在各流水線的佔用模式（第 k 位為 1 表示佔用第 k 個時間單位）。
• 狀態 s[5] 表示當前所有已啟動任務在各流水線的佔用情況（位掩碼 OR 合併）。
• 合法性判斷：新任務延遲 k 啟動，需 (s[i] >> k) & w[i] == 0 對所有流水線成立。

關鍵剪枝策略

1. 預計算合法延遲：jump[] 存儲所有滿足 judge(w, k) 的 k 值（相對啟動間隔）。
2. 下界剪枝：當前已用時間 sum + 剩餘任務數 × jump[0] (最小合法間隔) ≥ ans → 剪枝。

DFS 遞歸

void dfs(int *s, int depth, int sum) {
    if (sum + jump[0] * (10 - depth) > ans) return; // 剪枝 2
    if (depth == 10) { ans = min(ans, sum); return; }
    for (int k : jump) {
        if (judge(s, k)) {
            int ns[5];
            for (int i=0;i<5;i++) ns[i] = (s[i] >> k) | w[i]; // 更新狀態
            dfs(ns, depth+1, sum + k);
        }
    }
}

初始調用

第一個任務在第 0 時刻啟動，初始狀態 s = w，depth=1，sum=n（任務本身長度）。

複雜度

狀態空間極小（5 條線，任務模式固定），剪枝極其有效，瞬間求解。