合併成本 題解｜APCS 2024 年 1 月高級 第 4 題

前置知識

這題是區間 DP 的標準題，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

  • 區間 DP：NTUCPC Guide〈區間 DP〉——「dp[l][r] 只看最後一步切在哪」的想法，那一頁的習題正是本題；吳邦一《AP325》第 6 章的 P-6-17「切棍子」（教材 PDF 第 208～210 頁）用同一個遞迴式寫了 top-down 與 bottom-up 兩個版本。
  • 遞迴與記憶化：NTUCPC Guide〈遞迴〉——先寫會重複計算的遞迴，再加一張「小抄」存算過的答案。
  • 前綴和：NTUCPC Guide〈前綴和與差分〉——一段連續的和用兩個前綴和相減。

簡潔題意

\(n\) 個整數排成一列，每次挑相鄰的兩個數 \(u, v\) 合併成 \(u + v\)，花費 \(|u - v|\)。求合到只剩一個數的最小總花費（\(1 \le n \le 100\)，\(-1000 \le a_i \le 1000\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(30\) 分）：\(n \le 13\)。
  • 子題組 2（\(70\) 分）：無額外限制。

先拿下 30 分：只看最後一次合併

合併是把相鄰的兩個數變成一個，所以任何時候列上的每個數，都是原本一段連續的數的總和。最後一次合併時列上只剩兩個數：左邊是 \(a_l \ldots a_{mid}\) 的總和、右邊是 \(a_{mid+1} \ldots a_r\) 的總和，花費是兩個總和相減的絕對值；而在那之前，左右兩段各自已經合成一個數了，彼此互不干涉。於是

cost(l, r) ＝ 把 \(a_l \ldots a_r\) 合成一個數的最小花費 ＝ 對每個切點 \(mid\) 取 \(\text{cost}(l, mid) + \text{cost}(mid+1, r) + |S(l, mid) - S(mid+1, r)|\) 的最小值（\(S\) 是區間和）；只有一個數時是 \(0\)。

圖 1 把範例 1 的三種切法都算出來：切在第 3 個數之後最便宜，\(4 + 0 + 1 = 5\)。

圖 1：範例 1「3 −1 2 5」最後一次合併的三種切法，總花費分別是 10、12、5，最小的 5 就是答案

照定義寫成遞迴，區間和用前綴和相減：

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> prefix;                              // prefix[i] = a[1] + ... + a[i]

int sumOf(int l, int r) { return prefix[r] - prefix[l - 1]; }

// 把 a[l..r] 合成一個數的最小花費
int cost(int l, int r) {
    if (l == r) return 0;                        // 只有一個數：不用合併
    int best = INT_MAX;
    for (int mid = l; mid < r; mid++)            // 最後一次合併：左半 a[l..mid]、右半 a[mid+1..r]
        best = min(best, cost(l, mid) + cost(mid + 1, r) + abs(sumOf(l, mid) - sumOf(mid + 1, r)));
    return best;
}

int main() {
    cin >> n;
    prefix.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }
    cout << cost(1, n) << '\n';
    return 0;
}

這個遞迴會把同一段區間算很多次：\(n = 13\) 瞬間跑完，\(n = 20\) 本站實測 \(3\) 秒、\(n = 21\) 就要 \(9\) 秒。子題組 1 的 \(30\) 分穩穩到手。

從 30 分到 100 分：算過的區間記下來

不同的 \((l, r)\) 只有 \(O(n^2)\) 組，慢是因為同一組被反覆呼叫。開一張 memo[l][r]，算過就存起來、下次直接拿——程式只多三行：

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> prefix;
vector<vector<int>> memo;                        // memo[l][r]：算過的 cost(l, r)；-1 ＝ 還沒算過

int sumOf(int l, int r) { return prefix[r] - prefix[l - 1]; }

int cost(int l, int r) {
    if (l == r) return 0;
    if (memo[l][r] != -1) return memo[l][r];     // 算過就直接拿
    int best = INT_MAX;
    for (int mid = l; mid < r; mid++)
        best = min(best, cost(l, mid) + cost(mid + 1, r) + abs(sumOf(l, mid) - sumOf(mid + 1, r)));
    return memo[l][r] = best;
}

int main() {
    cin >> n;
    prefix.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }
    memo.assign(n + 1, vector<int>(n + 1, -1));
    cout << cost(1, n) << '\n';
    return 0;
}

每個區間第一次算時掃 \(O(n)\) 個切點，總共 \(O(n^3)\)，\(n = 100\) 只有 \(10^6\) 次。總和最多 \(100 \times 1000 = 10^5\)、每次合併花費最多 \(2 \times 10^5\)、\(99\) 次合併加起來不到 \(2 \times 10^7\)，int 綽綽有餘。

另一種寫法：不遞迴，照區間長度由短到長填表

dp[l][r] 需要的都是更短的區間，所以長度 \(1\)（全是 \(0\)）、長度 \(2\)、長度 \(3\)……照順序填，填到 dp[1][n] 就是答案。別寫成「\(l\) 由小到大、\(r\) 由小到大」：算 dp[l][r] 時右半段 dp[mid + 1][r] 還沒算過。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));   // dp[l][r]：a[l..r] 合成一個數的最小花費；長度 1 ＝ 0
    for (int len = 2; len <= n; len++)           // 先算短的區間，長的才有東西可以查
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INT_MAX;
            for (int mid = l; mid < r; mid++) {
                int left = prefix[mid] - prefix[l - 1], right = prefix[r] - prefix[mid];
                dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r] + abs(left - right));
            }
        }
    cout << dp[1][n] << '\n';
    return 0;
}

測過再交：範例沒有「只有一個數」

三個範例都有正有負、\(n \ge 4\)。沒蓋到：只有一個數、兩個數的最大花費、全部相同、全部是 \(0\)，以及貪心（每次合相差最小的一對）會錯的局面。

輸入 正確輸出 這一筆在測什麼
1 ／ 7 0 只有一個數：不用合併
2 ／ -1000 1000 2000 單次合併的最大花費；差值忘了取絕對值會印 -2000
3 ／ 5 5 5 5 先合哪兩個都一樣：\(5 + 5\) 免費，再和 \(5\) 合併花 \(5\)
4 ／ 1 3 3 1 4 每次都合「相差最小」的那一對（先合中間的 \(3, 3\)）會印 11
5 ／ 0 0 0 0 0 0 答案 \(0\) 的極端
3 ／ -3 3 -3 9 有負數：合併後的數可能變小（\(-3 + 3 = 0\)）；填表順序寫錯會印 3
用程式造：\(n = 100\)，\(1000\) 與 \(-1000\) 交替 100000 最大測資，\(O(n^3)\) 瞬間跑完

七筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 合併費用寫成 \(u + v\)：那是「合併果子」的公式，這題是 \(|u - v|\)——三個範例印 14、-20、-46。
  • 差值忘了取絕對值：三個範例印 -14、-19、-23。
  • 每次都合併相差最小的相鄰兩數：貪心不對，三個範例印 6、24、55；自測表第 4 列印 11。
  • 填表順序用「\(l\) 由小到大」：算 dp[l][r] 時 dp[mid + 1][r] 還是初始值，三個範例印 3、5、7；要照區間長度由短到長。
  • dp[l][r] 忘了先設成很大的數再取 min：全部停在 \(0\)，三個範例都印 0。
  • 30 分版直接交：不記小抄的遞迴 \(n = 21\) 本站實測 \(9\) 秒，\(n = 100\) 跑不完，子題組 2 整組超時。