HDU 4824 Disk Schedule：雙調歐幾里得旅行商問題在磁盤調度中的應用

問題背景

磁盤有多條軌道，每條軌道分為 360 個扇區。磁頭可順/逆時針旋轉（一周 360 時間單位），或跳轉相鄰軌道（每跳 400 時間單位），讀取數據需 10 時間單位。給定一組讀取請求（每軌道最多一個），磁頭從 (0,0) 出發，完成所有讀取後須返回原點，求最小總時間。

核心洞察：雙調旅行商問題

將每個請求視為平面上的點：x 軸為軌道號，y 軸為扇區角度（0~359）。磁頭移動代價為：

• 同軌道旋轉：min(|ΔS|, 360-|ΔS|)
• 換軌：400 * |ΔT|，且扇區位置不變

由於軌道號單調遞增（輸入已排序），最優路徑必為「雙調」：從最左點（軌道 0）嚴格向右至最右點，再嚴格向左返回起點。這將問題轉化為經典的 Bitonic TSP，可用 O(N^2) DP 求解。

動態規劃設計

設 dp[i][j] (i > j) 表示已訪問前 i 個點，兩條路徑分別終止於點 i 和點 j 的最小代價。轉移：

dp[i][j] = dp[i-1][j] + dist(i-1, i)          (j < i-1)
dp[i][i-1] = min_{k < i-1} (dp[i-1][k] + dist(k, i))

最終答案為 min_{i < n} (dp[n][i] + dist(i, n)) 加上固定開銷（每請求 10 讀取時間，軌道跳轉總時間）。

關鍵代碼片段

int dis(int x, int y) {          // 同軌道旋轉距離
    if (d[x] < d[y]) swap(x, y);
    int diff = d[x] - d[y];
    return min(diff, 360 - diff);
}

void init() { dp[1][0] = dis(0, 1); }

int DP() {
    for (int i = 2; i <= n; ++i) {
        dp[i][i-1] = INF;
        for (int j = 0; j < i-1; ++j) {
            dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(i, j));
            dp[i][j] = dp[i-1][j] + dis(i, i-1);
        }
    }
    int ans = INF;
    for (int i = 0; i < n; ++i) ans = min(ans, dp[n][i] + dis(i, n));
    return ans;
}

總結

本題巧妙地將磁盤調度建模為幾何上的雙調 TSP，利用單調性將 NP-Hard 問題降為多項式可解。實現時注意坐標變換與固定代價的加總。