UVA 1474：Evacuation Plan（撤離規劃——DP 最小匹配距離）

問題：n 個施工隊、m 個避難所 (n ≥ m)，各自位置已知。每隊分配到一個避難所，每所至少一隊，最小化總移動距離。

DP 設計

將施工隊與避難所按位置排序。定義 dp[i][j]：前 i 隊使用前 j 所的最小總距離。因已排序，最優匹配滿足單調性（不交叉），轉移：

dp[i][j] = min(
    dp[i-1][j-1] + |pos[i] - shelter[j]|,  // 第 i 隟配第 j 所
    dp[i-1][j]   + |pos[i] - shelter[j]|   // 第 i 隊也配第 j 所（多隊同所）
)

用滾動數組優化空間至 O(m)。path[i][j] 記錄決策用於回溯輸出分配方案。

代碼核心

for (int i=1; i<=n; i++) {
    for (int j=1; j<=m && j<=i; j++) {
        if (dp[v][j-1] < dp[v][j]) {
            dp[u][j] = dp[v][j-1] + abs(s[i].d - p[j].d);
            path[i][j] = 1;
        } else {
            dp[u][j] = dp[v][j] + abs(s[i].d - p[j].d);
            path[i][j] = 0;
        }
    }
}

經典有序匹配 DP，類似「郵局建立」問題變體。