題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟡 AT_dp_n Slimes

Problem Statement

題目簡述

有 $N$ 個史萊姆排成一列，第 $i$ 個史萊姆的大小為 $a_i$ 。每次可以選擇相鄰的兩個史萊姆合併成一個，合併後的大小為兩者之和，且需支付等同於合併後大小的成本。求將所有史萊姆合併成一個所需的最小總成本。

Constraints

約束條件

$2 \le N \le 400$
$1 \le a_i \le 10^9$
答案可能超過 32-bit 整數範圍

思路：區間 DP

這是經典的石子合併問題，使用區間 DP 來解決。

狀態定義

定義 $f[l][r]$ 為將區間 $[l, r]$ 內的所有史萊姆合併成一個所需的最小成本。

狀態轉移

對於區間 $[l, r]$ ，我們枚舉最後一次合併的分界點 $k$ （ $l \le k < r$ ）：

先將 $[l, k]$ 合併成一個史萊姆，成本為 $f[l][k]$
再將 $[k+1, r]$ 合併成一個史萊姆，成本為 $f[k+1][r]$
最後將這兩個史萊姆合併，成本為 $\sum_{i=l}^{r} a_i$

f[l][r] = \min_{l \le k < r} \left( f[l][k] + f[k+1][r] + \sum_{i=l}^{r} a_i \right)

邊界條件

$f[i][i] = 0$ ：單個史萊姆不需要合併。

遍歷順序

由於 $f[l][r]$ 依賴於更小的區間，需按照區間長度由小到大的順序計算。程式碼中以區間長度 $\text{ln}$ 為外層迴圈（從 $2$ 到 $N$ ），內層枚舉左端點 $l$ ，並由 $r = l + \text{ln} - 1$ 計算右端點，確保計算 $f[l][r]$ 時所有子區間都已計算完畢。

複雜度分析

時間複雜度： $\mathcal{O}(N^3)$ ，枚舉所有區間 $O(N^2)$ 並在每個區間內枚舉分界點 $O(N)$ 。
空間複雜度： $\mathcal{O}(N^2)$ ，用於儲存 DP 陣列。

Code

from itertools import accumulate

def solve():
    n = int(input())
    A = list(map(int, input().split()))
    assert len(A) == n

    s = list(accumulate(A, initial=0))

    # @cache
    # def dfs(l, r):
    #     if l == r:
    #         return 0
    #     res = float('inf')
    #     for i in range(l, r):
    #         res = min(res, dfs(l, i) + dfs(i + 1, r) + s[r + 1] - s[l])
    #     return res
    # print(dfs(0, n - 1))

    f = [[float('inf')] * n for _ in range(n)]
    for l in range(n):
        f[l][l] = 0
    for ln in range(2, n + 1):
        for l in range(n - ln + 1):
            r = l + ln - 1
            f[l][r] = min(f[l][k] + f[k + 1][r] + s[r + 1] - s[l] for k in range(l, r))
    print(f[0][n - 1])

if __name__ == "__main__":
    solve()