前置知識

這題是「遞迴切割」加「前綴和」，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 遞迴：NTUCPC Guide〈遞迴〉（終止條件＋「假裝函式已經寫好」）；吳邦一《AP325》第 1 章 1.2「實作遞迴定義」的 P-1-3「棍子中點切割」是本題的雙胞胎（只差切點的定義），本題是它後面的習題 Q-1-4（教材 PDF 第 20～24 頁；Python 版第 1 章）。
• 前綴和：NTUCPC Guide〈前綴和與差分〉——要帶走的是「任何一段的和＝兩個前綴和相減」。

簡潔題意

數列 \(a_0, a_1, \ldots, a_{n-1}\) 是一排位置上的重量。切一段 \([l, r]\) 時只能選內部的位置 \(p\)（\(l < p < r\)）當支點，讓失衡量 \(\left|\sum_{i=l}^{r} (i - p)\, a_i\right|\) 最小，一樣小就選最左邊的；取走支點的重量，左右兩段各自用同樣的規則繼續切。第一刀是深度 \(1\)，深度超過 \(K\) 或一段不到 \(3\) 個數就不切。求取走的重量總和（\(n \le 50000\)、\(0 \le K < 30\)、\(\sum a_i \le 10^9\)；APCS 逐筆給分）。

失衡量怎麼一口氣算完：兩個前綴和

\(\sum (i - p)\, a_i\) 拆開就是 \(\sum i\, a_i - p \sum a_i\)。令這一段的總重 \(W = \sum a_i\)、「位置乘重量」的總和 \(M = \sum i\, a_i\)，失衡量就是 \(|M - pW|\)——\(W\) 和 \(M\) 對一段來說是固定的，換支點只是換 \(p\)。所以先做兩個前綴和：sumA[i]＝前 \(i\) 個的 \(\sum a\)、sumIA[i]＝前 \(i\) 個的 \(\sum i\, a\)，任何一段的 \(W\)、\(M\) 都是兩個前綴和相減。

找支點就是在內部位置 \(l + 1 \sim r - 1\) 掃一遍 \(|M - pW|\)，取最小、相同取最左（用 < 比較，後面的平手不會取代前面的）。\(M\) 最大約 \(5 \times 10^4 \times 10^9 = 5 \times 10^{13}\)，pW 同一個量級——都要 long long。

切一刀就是同一個問題再做兩次：遞迴

寫一個函式 cut(l, r, depth)：這一段不到 \(3\) 個數、或 depth > K 就回傳 \(0\)；否則找出支點 \(p\)，回傳 \(a_p\) 加上左段 cut(l, p - 1, depth + 1) 加上右段 cut(p + 1, r, depth + 1)。從 cut(0, n - 1, 1) 開始——第一刀是深度 \(1\)，所以 \(K = 0\) 時連第一刀都不切、答案 \(0\)。

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

const int MAX_N = 50005;
int n, K;
long long a[MAX_N];
long long sumA[MAX_N + 1], sumIA[MAX_N + 1];   // 前綴和：sumA[i] = a[0..i-1] 的和、sumIA[i] = (j * a[j]) 的和

// 切 [l, r] 這一段，回傳這一段（含往下所有切割）取走的重量總和
long long cut(int l, int r, int depth) {
    if (r - l + 1 < 3 || depth > K) return 0;        // 不到 3 個數、或深度用完：不切
    long long W = sumA[r + 1] - sumA[l];             // 這一段的總重
    long long M = sumIA[r + 1] - sumIA[l];           // 這一段的「位置 × 重量」總和
    int best = l + 1;                                // 支點只能在內部：l+1 ~ r-1
    for (int p = l + 2; p <= r - 1; p++) {
        if (llabs(M - p * W) < llabs(M - best * W))  // 嚴格小於：平手留最左邊的
            best = p;
    }
    return a[best] + cut(l, best - 1, depth + 1) + cut(best + 1, r, depth + 1);
}

int main() {
    cin >> n >> K;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        sumA[i + 1] = sumA[i] + a[i];
        sumIA[i + 1] = sumIA[i] + (long long)i * a[i];
    }
    cout << cut(0, n - 1, 1) << '\n';
    return 0;
}

運算量：同一個深度的各段互不重疊，加起來不超過 \(n\) 個位置，每個位置的失衡量 \(O(1)\)；深度最多 \(K < 30\) 層，總共不到 \(30 \times 50000 = 1.5 \times 10^6\) 次——遞迴最深 \(K\) 層，堆疊不是問題。

測過再交：範例的支點平手只出現過一次

範例 2 的左段 \([2, 4, 1, 3]\) 是題目唯一一次平手（\(p = 1\) 和 \(p = 2\) 失衡量都是 \(5\)）。沒蓋到的：\(K = 0\)、剛好 \(3\) 個數、重量全相同、支點被逼到最邊邊（\(l + 1\) 或 \(r - 1\)）。

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