貨物運送 題解|APCS 2026 年 3 月高級 第 3 題
前置知識
這題的關鍵在 DP 的狀態怎麼設計,下面的講解直接把基本的 DP 觀念當成已知,沒讀過的先讀:
- 動態規劃的狀態設計:NTUCPC Guide〈動態規劃:狀態與轉移〉——狀態要記住「會影響接下來怎麼做」的事,而且只記這些。吳邦一《AP325》第 6 章「動態規劃」也有完整講解。
簡潔題意
兩名配送員都從地點 \(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)\)。