# APCS實作題2024年1月第4題：合併成本 > 日期：2024年8月17日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=m934) ## 題目 ### 問題描述 有 $n$ 個數字排成一列，依序是 $a_1, a_2, \dots, a_n$。 每次可以挑選兩個相鄰的數字 $(u, v)$ 合併，合併會花費 $|u - v|$ 的元，合併起來的數字會變為 $u+v$。 問把 $n$ 個東西合成一個數字的最小花費是多少？ <br /> ### 輸入說明 第一行有一個正整數 $n~(1 \leq n \leq 100)$，表示有多少個東西。 第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n ~(|a_i| \leq 1000)$，相鄰兩個數字之間用空格隔開。 子題分數： - 30%：$n \leq 13$ - 70%：無額外限制 <br /> ### 輸出格式 輸出最小花費。 <br /> ### 範例輸入1 ``` 4 3 -1 2 5 ``` ### 範例輸出1 ``` 5 ``` ### 範例輸入2 ``` 6 -5 3 0 -4 3 -2 ``` ### 範例輸出2 ``` 18 ``` ### 範例輸入3 ``` 7 -1 -6 6 -8 7 0 -9 ``` ### 範例輸出3 ``` 36 ``` <br /><br /> ## Python 程式碼 其中第15行，計算 [i, j] 區間成本的算法分成3段，第1段用遞迴計算 [i, k] 區間成本，第2段用遞迴計算 [k+1, j] 區間成本，第3段計算 [i, k] 及 [k+1, j] 兩區加總後相減的絕對值，即 $$ |rsum - lsum| = |(tot - lsum) - lsum| = |tot - 2 \times lsum| $$ 費時最久約為 0.2 s，使用記憶體最多約為 3.6 MB，通過測試。 ```python= n = int(input()) # 讀取資料數量 n a = list(map(int, input().split())) # 讀取資料 psum = [0]*(n+1) # 前綴和 for i in range(1, n+1): psum[i] += psum[i-1] + a[i-1] dp = [[-1]*(n+1) for _ in range(n+1)] # dp，記錄合併 [i][j] 區間最小的成本，預設為 -1 for i in range(n+1): dp[i][i] = 0 # dp[i][i] 為同一個數字，不用合併，成本為0 def solve(i, j): # 找 [i, j] 區間合併的最小成本 if dp[i][j] != -1: return dp[i][j] # 如果不是 -1，已找過，直接回傳值 imin = 1000000 # 最低成本，預設為超出題目範圍的值 tot = psum[j] - psum[i-1] # [i, j] 區間的和 #print("i = {:d}, j = {:d}, tot = {:d}".format(i, j, tot)) # 除錯用 for k in range(i, j): # 掃過 [i, j] 區間，k 不包含 j lsum = psum[k] - psum[i-1] # [i, k] 區間和 tmp = solve(i, k) + solve(k+1, j) + abs(tot - lsum - lsum) # 遞迴，找 [i, k] 及 [k+1, j]，再加上這個區的成本 if tmp < imin: imin = tmp # 如果 tmp 小於 imin，更新 imin dp[i][j] = imin # 存入 dp return imin # 回傳 imin ans = solve(1, n) # 代入 [1, n] 求答案 print(ans) # 印出答案 ``` <br /> 如果將串列 a 直接轉為前綴和，理論上可以再少用一點記憶體，但是這題的資料量不大，看不出效果。費時最久約為 0.2 s，使用記憶體最多約為 3.6 MB，通過測試。 ```python= n = int(input()) # 讀取資料數量 n a = [0] # 儲存資料用的串列，之後會轉為前綴和 a += list(map(int, input().split())) # 讀取資料 for i in range(1, n+1): a[i] += a[i-1] dp = [[-1]*(n+1) for _ in range(n+1)] # dp，記錄合併 [i][j] 區間最小的成本，預設為 -1 for i in range(n+1): dp[i][i] = 0 # dp[i][i] 為同一個數字，不用合併，成本為0 def solve(i, j): # 找 [i, j] 區間合併的最小成本 if dp[i][j] != -1: return dp[i][j] # 如果不是 -1，已找過，直接回傳值 imin = 1000000 # 最低成本，預設為超出題目範圍的值 tot = a[j] - a[i-1] # [i, j] 區間的和 #print("i = {:d}, j = {:d}, tot = {:d}".format(i, j, tot)) # 除錯用 for k in range(i, j): # 掃過 [i, j] 區間，k 不包含 j lsum = a[k] - a[i-1] # [i, k] 區間和 tmp = solve(i, k) + solve(k+1, j) + abs(tot - lsum - lsum) # 遞迴，找 [i, k] 及 [k+1, j]，再加上這個區的成本 if tmp < imin: imin = tmp # 如果 tmp 小於 imin，更新 imin dp[i][j] = imin # 存入 dp return imin # 回傳 imin ans = solve(1, n) # 代入 [1, n] 求答案 print(ans) # 印出答案 ``` <br /><br /> ## C++ 程式碼 費時最久約為 51 ms，使用記憶體最多約為 488 kB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <cmath> using namespace std; int solve(int i, int j, vector<vector<int>>& dp, vector<int> a) { // 找 [i, j] 區間合併的最小成本 if (dp[i][j] != -1) return dp[i][j]; // 如果不是 -1，已找過，直接回傳值 int imin = 1000000; // 最低成本，預設為超出題目範圍的值 int tot = a[j] - a[i-1]; // [i, j] 區間的和 for(int k=i; k<j; k++) { // 掃過 [i, j] 區間，k 不包含 j-1 int lsum = a[k] - a[i-1]; // [i, k] 區間和 int tmp = solve(i, k, dp, a) + solve(k+1, j, dp, a) + abs(tot - lsum - lsum); // 遞迴，找 [i, k] 及 [k+1, j]，再加上這個區的成本 if (tmp < imin) imin = tmp; // 如果 tmp 小於 imin，更新 imin } dp[i][j] = imin; // 存入 dp return imin; // 回傳 imin } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; // 讀取資料數量 n vector<int> a (n+1, 0); // 儲存資料用的串列，轉為前綴和 for(int i=1; i<=n; i++) { int tmp; cin >> tmp; a[i] = a[i-1] + tmp; } vector<vector<int>> dp (n+1, vector<int> (n+1, -1)); // dp，記錄合併 [i][j] 區間最小的成本，預設為 -1 for(int i=0; i<=n; i++) dp[i][i] = 0; // dp[i][i] 為同一個數字，不用合併，成本為0 int ans = solve(1, n, dp, a); // 代入 [1, n] 求答案 cout << ans << "\n"; // 印出答案 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`