貨物運送 題解|APCS 2026 年 3 月高級 第 3 題


前置知識

這題的關鍵在 DP 的狀態怎麼設計,下面的講解直接把基本的 DP 觀念當成已知,沒讀過的先讀:

簡潔題意

兩名配送員都從地點 \(1\) 出發,依序處理 \(k\) 件貨物(目的地 \(p_1, p_2, \ldots, p_k\) 互異),每件選一人從目前位置直接移到 \(p_i\)、另一人不動;全部送完後兩人都要直接移到地點 \(n\)。從 \(u\) 直接到 \(v\) 的費用是 \(c_{u,v}\),求最小總費用(\(2 \le n \le 2000\),\(1 \le k \le n\),\(0 \le c_{u,v} \le 50\),\(c\) 對稱、對角線是 \(0\),不保證三角不等式,所以不能用繞路代替直接移動)。(APCS 逐筆給分。)

送完一件貨,一定有人站在那裡

每件都要有人送到,所以剛送完第 \(i\) 件時,其中一人就在 \(p_i\);另一個人在哪?他上一次送的是某一件 \(p_j\)(\(j < i\)),或者還沒動過、在起點(把起點記成 \(p_0 = 1\))。而且兩個人沒有名字之分,只要知道「閒著的那個人在 \(p_j\)」就夠了。

狀態只記「閒著的人在哪」

令 dp[i][j](\(j < i\))為送完第 \(i\) 件、閒著的人在 \(p_j\) 的最小費用。從 dp[i - 1][j] 送第 \(i\) 件有兩種選擇:

  • 剛送完第 \(i - 1\) 件的人繼續送:閒著的人不變,dp[i][j] = dp[i - 1][j] + c[p[i - 1]][p[i]]。
  • 換閒著的人去送:剛送完第 \(i - 1\) 件的人變成閒的,dp[i][i - 1] = min(dp[i - 1][j] + c[p[j]][p[i]]),對所有 \(j\) 取最小。

起點 dp[0][0] = 0(兩人都在地點 \(1\))。最後兩人都要到 \(n\):答案是 \(\min_j \left( \text{dp}[k][j] + c_{p_k, n} + c_{p_j, n} \right)\),別忘了閒著的那個人也要走這一趟。

狀態 \(O(k^2)\)、每個轉移 \(O(1)\),\(k \le 2000\) 時約 \(4 \times 10^6\) 次。讀入 \(n^2 = 4 \times 10^6\) 個整數比 DP 本身還花時間。

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 2000;
const int INF = 1000000000;
int n, k;
int p[MAX_N + 1];              // p[0] = 1(兩人的起點),p[1..k] 是依序的目的地
int cost[MAX_N + 1][MAX_N + 1];
int dp[MAX_N + 1][MAX_N + 1];  // dp[i][j]:送完第 i 件(有人在 p[i]),另一人在 p[j] 的最小費用

int main() {
    cin >> n >> k;
    p[0] = 1;
    for (int i = 1; i <= k; i++) cin >> p[i];
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++) cin >> cost[u][v];
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= k; j++) dp[i][j] = INF;
    dp[0][0] = 0;  // 兩人都在地點 1
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j <= i - 1; j++) {
            if (dp[i - 1][j] == INF) continue;  // j = i-1 只有在 i = 1(兩人都在起點)時有效
            // 剛送完第 i-1 件的那個人繼續送第 i 件,另一人留在 p[j]
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + cost[p[i - 1]][p[i]]);
            // 換另一人(在 p[j])去送第 i 件,原本在 p[i-1] 的人變成閒的那個
            dp[i][i - 1] = min(dp[i][i - 1], dp[i - 1][j] + cost[p[j]][p[i]]);
        }
    }
    // 最後兩人都要到地點 n
    int answer = INF;
    for (int j = 0; j < k; j++)
        answer = min(answer, dp[k][j] + cost[p[k]][n] + cost[p[j]][n]);
    cout << answer << '\n';
    return 0;
}

測過再交:範例沒有只送一件的情況

兩個範例送 \(3\) 件和 \(6\) 件,答案是 \(28\) 和 \(35\)。沒蓋到的:只送一件(閒著的人從頭到尾沒動過)、繞路比直接走便宜很多的情況,還有 \(n = k = 2000\) 的大輸入。

輸入 正確輸出 這一筆在測什麼
2 1 / 2 / 0 5 / 5 0 10 只送一件:送貨的人 \(1 \to 2\),沒動過的人最後也要 \(1 \to 2\)
3 2 / 2 3 / 0 1 50 / 1 0 1 / 50 1 0 52 不能繞路:不管怎麼分,總有一個人得直接 \(1 \to 3\)(花 \(50\));能繞路的話 \(1 \to 2 \to 3\) 只要 \(2\)
用程式造:\(n = k = 2000\),目的地 \(2000, 1999, \ldots, 1\),\(c_{u,v} = (u + v) \bmod 51\)(\(u \ne v\)) 47892 最大的輸入:讀 \(4 \times 10^6\) 個數、DP 表 \(2001 \times 2001\)

三筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 每件都派離目的地比較近的人去送(貪心):眼前省一點,可能讓之後的路變長。範例 1 就會印 32。
  • 先跑 Floyd–Warshall,把繞路的費用當成兩點之間的費用:題目規定要直接移動。範例 1 就會印 25;自測表第 2 列印 4。
  • 忘了閒著的那個人最後也要走到 \(n\):範例 1 就會印 23;自測表第 1 列印 5。
  • 枚舉每件貨物給誰送(\(2^k\) 種):\(k\) 很小時沒問題,範例全過;\(k = 2000\) 時 \(2^{2000}\) 種根本跑不完,本站 \(20\) 筆有 \(11\) 筆超時。
  • 只記「兩個人各在哪」當狀態:\(n^2 = 4 \times 10^6\) 個狀態、每件貨物都要掃一遍,\(O(k n^2)\) 太慢。閒著的人只可能在 \(p_0, p_1, \ldots, p_{i-1}\) 這 \(i\) 個地方,狀態只要 \(O(k^2)\)。