区间 DP：石子合并

// 石子合并 —— 暴力：DFS 枚举「这一步合并哪一对相邻的堆」
//
// ★ 它是**完全不同的思路**，这一点是特意的（第 20 章那条规矩：
//   标准答案最好用完全不同的思路写出来）。
//   这份代码里**没有区间、没有 f 表、没有断点**，它就是老老实实地在合并石子：
//   手里拿着当前这一排堆，挑一对相邻的合掉，付出它们的和，然后接着挑。
//   正解那边则是「枚举最后一次合并的断点」—— 两边连看问题的角度都不一样，
//   所以它们对上了才有说服力。
//
// 复杂度 (n-1)!：第一步有 n-1 对相邻可选，合完剩 n-1 堆，于是又有 n-2 对……
//   n = 10 是 362 880 条路径，n = 12 就是 4 千万条 —— 正文第 11 步会实测这条曲线。
//
// ⚠ 这里**故意一句剪枝都不写**（连「已经比当前最优差了就不往下走」都没有）。
//   第 25 章那张耗时对比表差点做废，就是因为暴力里有一句免费的剪枝，
//   把整棵树剪没了、暴力假装自己不慢。要拿它证明「暴力有多慢」，
//   就得让它老老实实走完 (n-1)! 条路径。
//
// 题意：n 堆石子排成一排，每次只能合并**相邻**两堆，代价 = 两堆石子数之和。
//       求合并成一堆的**最小**总代价。
// 输入：第一行 n，第二行 n 个正整数
// 输出：最小总代价
//
// ⚠「只能合并相邻两堆」是这道题的全部难点所在。
//   要是允许任意两堆合并，它就是哈夫曼树，每次挑最小的两堆贪心就对了 ——
//   正文第 8 步会拿这个差别单独打一次假。

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

long long best;

// piles：当前这一排还剩下的堆；cost：已经付出的代价
void dfs(vector<long long>& piles, long long cost) {
    if (piles.size() == 1) { best = min(best, cost); return; }

    for (size_t i = 0; i + 1 < piles.size(); i++) {
        long long merged = piles[i] + piles[i + 1];
        vector<long long> nxt;
        nxt.reserve(piles.size() - 1);
        for (size_t t = 0; t < piles.size(); t++) {
            if (t == i) { nxt.push_back(merged); t++; }   // i 和 i+1 并成一堆
            else nxt.push_back(piles[t]);
        }
        dfs(nxt, cost + merged);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    best = LLONG_MAX;
    dfs(a, 0);
    cout << best << "\n";
    return 0;
}

// 石子合并 —— 记忆化搜索版（接第 17、21 章）
//
// ★ 这份代码存在的理由只有一个：**它不用你操心填表顺序。**
//
//   solve(l, r) 要用 solve(l, k) 和 solve(k+1, r)，就直接递归下去要 ——
//   谁先算谁后算，是递归自己安排的，你一个字都不用想。
//   而下一份 fast.cpp（递推）必须由你亲手安排这个顺序，
//   一旦安排错了，它不会报错、不会崩溃，只会安静地读到一格还没算的 0。
//
//   所以这一章的 ★（按区间长度从小到大填）本质上是：
//   **把递归替你做的那件事，自己做一遍。**
//   第 21 章「依赖谁，就先填谁」这句话，到这里是第四次登场了。
//
// 复杂度 O(n³)：状态 O(n²) 个，每个状态枚举 O(n) 个断点。和递推完全一样。
// 输入输出同 brute.cpp。
//
// ⚠ f 用 -1 表示「还没算过」，不能用 0 —— 长度为 1 的区间答案就是 0，
//   拿 0 当「没算过」的话，那些格子会被反复重算（虽然答案不错，但退化成指数）。

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

int n;
vector<long long> s;                    // s[i] = a[1] + … + a[i]，1 基下标（第 6 章的前缀和）
vector<vector<long long>> f;

long long solve(int l, int r) {
    if (l == r) return 0;               // 只剩一堆，不用合，代价 0
    if (f[l][r] >= 0) return f[l][r];

    long long best = LLONG_MAX;
    for (int k = l; k < r; k++)         // 枚举最后一次合并的断点：[l,k] 和 [k+1,r]
        best = min(best, solve(l, k) + solve(k + 1, r));

    // 最后那一次合并，把整个 [l,r] 合成一堆，代价就是这一段石子的总数
    return f[l][r] = best + s[r] - s[l - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n) || n <= 0) return 0;
    s.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) { long long x; cin >> x; s[i] = s[i - 1] + x; }

    f.assign(n + 1, vector<long long>(n + 1, -1));
    cout << solve(1, n) << "\n";
    return 0;
}

// 石子合并 —— 正解：区间 DP，★ 按区间长度从小到大填
//
// 状态：f[l][r] = 把第 l 堆到第 r 堆合并成一堆，最少要付多少代价。
// 转移：枚举**最后一次**合并的断点 k（左边 [l,k] 已经并成一堆、右边 [k+1,r] 也并成一堆）：
//
//       f[l][r] = min over k in [l, r-1] of ( f[l][k] + f[k+1][r] ) + (a[l] + … + a[r])
//
//   后面那一项和 k 无关 —— 不管怎么分，最后那一次合并总是把整段并成一堆，
//   代价恒等于这一段石子的总数。所以它可以提到 min 外面（第 6 章的前缀和 O(1) 求出来）。
//
// ★ 关键一步：**填表顺序按区间长度从小到大。**
//   因为 f[l][r] 要读 f[l][k] 和 f[k+1][r]，这两个区间都比 [l,r] **短**。
//   「依赖谁，就先填谁」（第 21 章）—— 短的先算好，长的才有得读。
//
//   ⚠ 注意这不是「从左到右」也不是「从右到左」：
//     l 从小到大、r 从小到大地填，f[k+1][r] 那一项就还没算（wrongOrder.cpp 演示了后果）。
//     而 l 从**大**到小、r 从小到大是**对的**（lrOrder.cpp）——
//     长度枚举只是「让依赖先算好」的一种实现方式，不是唯一的那一种。
//
// 复杂度 O(n³)、空间 O(n²)。n = 100 时约 100 万次转移，眨眼就跑完。
// 输入输出同 brute.cpp。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<long long> s(n + 1, 0);                  // 前缀和，1 基下标
    for (int i = 1; i <= n; i++) { long long x; cin >> x; s[i] = s[i - 1] + x; }

    vector<vector<long long>> f(n + 2, vector<long long>(n + 2, 0));
    // 长度为 1 的区间不用合并，代价 0 —— f 初值就是 0，所以不用另写一句

    for (int len = 2; len <= n; len++)              // ★ ① 先枚举区间长度，从短到长
        for (int l = 1; l + len - 1 <= n; l++) {    //   ② 再枚举左端点
            int r = l + len - 1;
            long long best = LLONG_MAX;
            for (int k = l; k < r; k++)             //   ③ 最后枚举断点
                best = min(best, f[l][k] + f[k + 1][r]);
            f[l][r] = best + s[r] - s[l - 1];       // 最后一次合并的代价：整段石子之和
        }

    cout << f[1][n] << "\n";
    return 0;
}

// 把整张 f 表**按长度一层一层**打印出来 —— 动画就是照着这个次序播的
//
// 为什么要有它：动画是用 TypeScript 把这个算法重写一遍画出来的。
// 只比最后那个答案是不够的 —— 答案蒙对、中间过程画错，学生一样看不出来。
// 所以这里把每一层（每一个区间长度）的整排 f 值和选中的断点 k 都打出来，
// check:viz 拿它和动画的每一帧**逐格**对照。
// （第 23 章那份 trace.cpp 是同样的用意，那次对的是每一步的整个 f 数组。）
//
// ★ 顺便，这个输出本身就是这一章的 ★ 的样子：
//   一层一层往上长，每一层都只用到**下面那些层**已经填好的值。
//   长度 1 那一层全是 0，是整张表的地基。
//
// 用法：./trace            （用正文那组默认数据 4 1 2 3 5）
//       ./trace < 数据文件（格式同 brute.cpp）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<long long> a;
    int n;
    if (cin >> n && n > 0) {
        a.resize(n);
        for (auto& x : a) cin >> x;
    } else {
        a = {4, 1, 2, 3, 5};                            // 正文默认数据
        n = (int)a.size();
    }

    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];

    cout << "石子：";
    for (int i = 0; i < n; i++) cout << (i ? " " : "") << a[i];
    cout << "\n\n";

    vector<vector<long long>> f(n + 2, vector<long long>(n + 2, 0));

    cout << "长度 1 :";
    for (int i = 1; i <= n; i++) cout << "  f[" << i << "][" << i << "]=0";
    cout << "        <- 地基：一堆不用合，代价 0\n";

    for (int len = 2; len <= n; len++) {
        cout << "长度 " << len << " :";
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            long long best = LLONG_MAX;
            int bk = l;
            for (int k = l; k < r; k++)
                if (f[l][k] + f[k + 1][r] < best) { best = f[l][k] + f[k + 1][r]; bk = k; }
            f[l][r] = best + s[r] - s[l - 1];
            cout << "  f[" << l << "][" << r << "]=" << f[l][r] << "(k=" << bk << ")";
        }
        cout << "\n";
    }

    cout << "\n答案 f[1][" << n << "] = " << f[1][n] << "\n";
    cout << "每一层用到的都只是下面那些层的值 —— 这就是「按区间长度从小到大」的全部含义。\n";
    return 0;
}

// 石子合并 —— 左端点从**大**到小、右端点从小到大。★ 它看着不像区间 DP，但它是对的。
//
// 这份代码存在的理由，和第 25 章那份 vol2In.cpp（外倒内正）一模一样：
// **要让学生知道「顺序」这件事的判据是依赖关系，不是某个固定的写法。**
//
// 拿转移来对一对：f[l][r] 要读 f[l][k]（k < r）和 f[k+1][r]（k+1 > l）。
//
//   · f[l][k]：同一个 l、更小的 r —— 内层 r 正序，这一轮**前面刚算过** ✓
//   · f[k+1][r]：更大的 l —— 外层 l 倒序，**上几轮就算完了** ✓
//
// 两个依赖都在手上，所以它给出的答案和按长度枚举**完全一样**。
// check:viz 拿 300 组随机数据钉死了这一条：它一轮都「抓不到」，因为它根本没错。
//
// ⚠ 那为什么正文还是推荐按长度写？
//   因为「短的先算」是一句**不用每次都重新推的**理由，而这份代码的正确性
//   每次都得把上面那两行依赖重新验一遍。**能不动脑子的地方就别动脑子。**
//
// 输入输出同 brute.cpp。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; i++) { long long x; cin >> x; s[i] = s[i - 1] + x; }

    vector<vector<long long>> f(n + 2, vector<long long>(n + 2, 0));

    for (int l = n; l >= 1; l--)                    // ★ 左端点倒序
        for (int r = l + 1; r <= n; r++) {          // ★ 右端点正序
            long long best = LLONG_MAX;
            for (int k = l; k < r; k++)
                best = min(best, f[l][k] + f[k + 1][r]);
            f[l][r] = best + s[r] - s[l - 1];
        }

    cout << f[1][n] << "\n";
    return 0;
}

// ✗ 错误版本一：左端点从小到大、右端点从小到大 —— 这一章最经典的错法。
//
// 这个写法看上去无比自然（「两重循环嘛，当然都从小到大」），而且**编译没有警告、
// 运行不会崩、答案还很像话** —— 它只是偏小一点点。这正是填表顺序类 bug 的可怕之处
// （第 21 章那份 triWrong.cpp 讲的是同一件事）。
//
// 错在哪：f[l][r] 要读 f[k+1][r]，而 k+1 > l ——
// **左端点更大的那些区间，在这个顺序下一个都还没算。**
// 读到的全是初值 0，于是「右半段的合并代价」被当成了免费的。
//
//   ⚠ 免费 = 更小，而这道题求的是最小值，所以错误答案**恒 ≤ 正确答案**。
//     一个偏小的答案在样例上很容易蒙对（样例通常很小），
//     300 组随机数据才是它的照妖镜 —— 正文第 12 步那张表。
//
// 输入输出同 brute.cpp。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; i++) { long long x; cin >> x; s[i] = s[i - 1] + x; }

    vector<vector<long long>> f(n + 2, vector<long long>(n + 2, 0));

    for (int l = 1; l <= n; l++)                    // ✗ 左端点正序
        for (int r = l + 1; r <= n; r++) {
            long long best = LLONG_MAX;
            for (int k = l; k < r; k++)
                best = min(best, f[l][k] + f[k + 1][r]);   // ← f[k+1][r] 还没算过
            f[l][r] = best + s[r] - s[l - 1];
        }

    cout << f[1][n] << "\n";
    return 0;
}

// 三种填表顺序并排跑成一张表 —— 顺带把「读到了还没算好的格子」这件事**数出来**
//
// 光说「顺序错了会读到还没算的值」是抽象的。这份代码给每一格挂一个 ready 标记，
// 转移时只要读到 ready = false 的格子就计一次数。于是「错在哪」变成了一个**数字**：
//
//   · 按区间长度从小到大        → 0 次    ✓
//   · 左端点倒序、右端点正序    → 0 次    ✓（它也是对的，见 lrOrder.cpp）
//   · 左端点正序、右端点正序    → 一堆    ✗
//
// ★ 而且第三行的答案不是「随机地偏小」，它**恒等于所有石子之和**。
//   两行推理：这个顺序下 f[k+1][r] 永远是 0，而 k = l 时 f[l][l] 也是 0，
//   所以 min 恒取到 0，f[l][r] 就成了 s[r] - s[l-1]。
//   换句话说，它精确地解了另一道题：**「允许一次把任意多个连续的堆合成一堆」**——
//   那道题当然是一口气全合掉最便宜，答案就是总和。
//   第 23、24、25 章一共钉死了五条这样的恒等式，这是第六条。
//
// 用法：./order            （用正文那组默认数据 4 1 2 3 5）
//       ./order < 数据文件（格式同 brute.cpp）
//
// ⚠ 表格对齐是手数空格数出来的，不是 setw ——
//   setw 数的是**字节数**，一个汉字 3 字节却只占 2 格宽（第 25 章踩过）。
//   含中文的那一列这里用 padDisp() 按**显示宽度**补空格。

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

// 按显示宽度补空格：ASCII 算 1 格，非 ASCII（这里只有汉字）算 2 格
static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;               // UTF-8 续字节，不算宽度
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

enum Order { BY_LEN, L_DOWN, L_UP };

// 返回 {答案, 读到「还没算好的格子」的次数}
static pair<long long, long long> solve(const vector<long long>& a, Order ord) {
    int n = (int)a.size();
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];

    vector<vector<long long>> f(n + 2, vector<long long>(n + 2, 0));
    vector<vector<bool>> ready(n + 2, vector<bool>(n + 2, false));
    for (int i = 1; i <= n; i++) ready[i][i] = true;    // 长度 1 的区间一开始就是算好的（0）

    long long dirty = 0;
    auto fill = [&](int l, int r) {
        long long best = LLONG_MAX;
        for (int k = l; k < r; k++) {
            if (!ready[l][k]) dirty++;
            if (!ready[k + 1][r]) dirty++;
            best = min(best, f[l][k] + f[k + 1][r]);
        }
        f[l][r] = best + s[r] - s[l - 1];
        ready[l][r] = true;
    };

    if (ord == BY_LEN) {
        for (int len = 2; len <= n; len++)
            for (int l = 1; l + len - 1 <= n; l++) fill(l, l + len - 1);
    } else if (ord == L_DOWN) {
        for (int l = n; l >= 1; l--)
            for (int r = l + 1; r <= n; r++) fill(l, r);
    } else {
        for (int l = 1; l <= n; l++)
            for (int r = l + 1; r <= n; r++) fill(l, r);
    }
    return {f[1][n], dirty};
}

int main() {
    // ⚠ 这份代码 cout 和 printf 混着用（表格用 printf 好对齐），
    //   所以**不能**关掉 ios::sync_with_stdio —— 关掉之后两边各自缓冲，
    //   打印出来的顺序会乱掉（表格跑到结语后面去）。这是踩出来的。
    vector<long long> a;
    int n;
    if (cin >> n && n > 0) {
        a.resize(n);
        for (auto& x : a) cin >> x;
    } else {
        a = {4, 1, 2, 3, 5};                            // 正文默认数据
    }

    long long total = 0;
    for (auto x : a) total += x;

    cout << "石子：";
    for (size_t i = 0; i < a.size(); i++) cout << (i ? " " : "") << a[i];
    cout << "   （共 " << a.size() << " 堆，总数 " << total << "）\n\n";

    cout << "  " << padDisp("填表顺序", 28) << "  答案   读到还没算好的格子   和正解一样\n";
    cout << "  " << string(28, '-') << "  ----   ------------------   ----------\n";

    const char* names[] = {"按区间长度从小到大", "左端点倒序、右端点正序", "左端点正序、右端点正序"};
    Order ords[] = {BY_LEN, L_DOWN, L_UP};
    long long right = solve(a, BY_LEN).first;

    for (int i = 0; i < 3; i++) {
        auto [ans, dirty] = solve(a, ords[i]);
        printf("  %s  %4lld   %18lld   %s\n",
               padDisp(names[i], 28).c_str(), ans, dirty, padDisp(ans == right ? "是" : "否", 10).c_str());
    }

    cout << "\n★ 「读到还没算好的格子」那一列只要不是 0，这个顺序就是错的。\n";
    cout << "  而最后一行的答案恒等于所有石子之和（" << total << "）——\n";
    cout << "  它不是随机地错，它精确地解了「允许一次合并任意多个连续堆」的那道题。\n";
    return 0;
}

// ✗ 错误版本四：贪心 —— 每次合并「相邻两堆里和最小的那一对」。
//
// ★ 这是这道题最经典的错误直觉，而且它错得很有来头：
//   **要是允许任意两堆合并（不必相邻），这个贪心就是对的** —— 那就是哈夫曼树，
//   每次挑最小的两堆合起来，是有严格证明的最优解（第 19 章那套交换论证）。
//
//   一旦加上「只能合并相邻两堆」，交换论证就断了：
//   你想把两堆小的换到一起先合，可它们中间隔着别的堆，**换不过去**。
//   第 20 章那句话在这里第二次兑现：
//   **贪心的正确性属于问题，不属于算法。** 同一个「先合最小的」，
//   在哈夫曼树上对，在石子合并上错。
//
// 这份代码用来做两件事：
//   ① 正文第 8 步拿它单独打一次假（对拍 300 轮，看它错多少轮）；
//   ② greedyFind.cpp 会枚举出让它失败的**最小反例**，
//      像第 20 章的 coinFind.cpp 一样，把「反例长什么样」这件事变成可看的东西。
//
// 并列时取最左边那一对（任何一种确定的取法都不影响结论，反例照样存在）。
// 输入输出同 brute.cpp。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    long long cost = 0;
    while (a.size() > 1) {
        size_t bi = 0;
        long long bs = LLONG_MAX;
        for (size_t i = 0; i + 1 < a.size(); i++)        // 找和最小的那一对相邻堆
            if (a[i] + a[i + 1] < bs) { bs = a[i] + a[i + 1]; bi = i; }
        cost += bs;
        a[bi] = bs;
        a.erase(a.begin() + bi + 1);
    }

    cout << cost << "\n";
    return 0;
}

// 找「每次合并最小的相邻两堆」这个贪心的**最小反例**（第 20 章 coinFind.cpp 的做法）
//
// 为什么值得单独写一份：
// 「这个贪心是错的」是一句空话，**一个具体的反例才是证据**，而且学生能自己动手验。
// 更有用的是它顺带回答了一个问题：**反例到底有多罕见？**
// 如果一万组里才有一组，那你随手造的数据当然抓不住它 —— 这正是第 20 章那张
// 「300 轮里错了几轮」的表想说的事。
//
// 做法：按「先比堆数、再比字典序」的顺序枚举所有小数据，
//       对每一组同时跑区间 DP（正解）和贪心，第一次不相等的就是最小反例。
//
// 用法：./greedyFind [最大堆数=5] [每堆最大石子数=6]
// 输出：每种堆数下的第一个反例、反例总数和占比。
//
// ⚠ 顺序是「堆数从小到大、同堆数按字典序」，所以「第一个」这件事是良定义的、可复现的。
//   第 20 章踩过的教训：找最小反例时如果枚举顺序含糊，两个人跑出来的「最小反例」会不一样。

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

// 按显示宽度补空格：ASCII 算 1 格，汉字算 2 格。
// ⚠ 不能用 setw / printf 的 %-Ns —— 它们数的是**字节数**，
//   一个汉字 3 字节却只占 2 格宽，含中文的列会歪掉（第 25 章踩过这个坑）。
static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

// 区间 DP 正解（和 fast.cpp 同一份转移）
static long long best(const vector<long long>& a) {
    int n = (int)a.size();
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];
    vector<vector<long long>> f(n + 2, vector<long long>(n + 2, 0));
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            long long b = LLONG_MAX;
            for (int k = l; k < r; k++) b = min(b, f[l][k] + f[k + 1][r]);
            f[l][r] = b + s[r] - s[l - 1];
        }
    return f[1][n];
}

// 贪心：每次合并相邻两堆里和最小的那一对（和 greedy.cpp 同一份逻辑）
static long long greedy(vector<long long> a) {
    long long cost = 0;
    while (a.size() > 1) {
        size_t bi = 0;
        long long bs = LLONG_MAX;
        for (size_t i = 0; i + 1 < a.size(); i++)
            if (a[i] + a[i + 1] < bs) { bs = a[i] + a[i + 1]; bi = i; }
        cost += bs;
        a[bi] = bs;
        a.erase(a.begin() + bi + 1);
    }
    return cost;
}

int main(int argc, char** argv) {
    int maxN = (argc > 1) ? atoi(argv[1]) : 5;
    int maxV = (argc > 2) ? atoi(argv[2]) : 6;

    cout << "枚举堆数 3 ~ " << maxN << "，每堆石子数 1 ~ " << maxV
         << "（按字典序），找贪心「每次合并最小的相邻两堆」的反例\n\n";
    cout << "  堆数   枚举组数   反例组数     占比   最小反例（字典序最小）   贪心 / 正解\n";
    cout << "  ----   --------   --------   ------   ----------------------   -----------\n";

    for (int n = 3; n <= maxN; n++) {
        vector<long long> a(n, 1);
        long long total = 0, bad = 0;
        vector<long long> firstBad;
        long long fg = 0, fb = 0;

        while (true) {
            total++;
            long long g = greedy(a), b = best(a);
            if (g != b) {
                bad++;
                if (firstBad.empty()) { firstBad = a; fg = g; fb = b; }
            }
            // 字典序 +1
            int i = n - 1;
            while (i >= 0 && a[i] == maxV) { a[i] = 1; i--; }
            if (i < 0) break;
            a[i]++;
        }

        string ex;
        if (firstBad.empty()) {
            ex = "（一个都没有）";
        } else {
            for (int i = 0; i < n; i++) ex += (i ? " " : "") + to_string(firstBad[i]);
        }
        printf("  %4d   %8lld   %8lld   %5.1f%%   %s   ",
               n, total, bad, 100.0 * bad / total, padDisp(ex, 22).c_str());
        if (firstBad.empty()) printf("%s\n", padDisp("贪心永远是对的", 11).c_str());
        else printf("%lld / %lld\n", fg, fb);
    }

    cout << "\n★ 反例的占比就是「随手造一组数据能抓住这个贪心」的概率。\n";
    cout << "  它同时解释了两件事：为什么这个错误直觉能骗过样例，\n";
    cout << "  以及为什么对拍必须跑几百轮而不是跑一轮。\n";
    return 0;
}

// 输出**合并方案** —— 还第 23 章欠下的那笔账
//
// 第 23 章末尾说过：「要方案就得开二维表」。一维滚动数组只留得下答案，
// 留不下「这个答案是怎么来的」。区间 DP 的 f 本来就是二维的，
// 所以只要再开一张同样大的 from[l][r] 记下**最优断点**，回溯就完事了 ——
// 和第 23 章 trace 那一套回溯是同一个套路，一个字都不用新学。
//
//   f[l][r]    = 把 [l,r] 合成一堆的最小代价
//   from[l][r] = 取到那个最小值的断点 k（最后一次合并是 [l,k] + [k+1,r]）
//
// ★ 回溯的顺序有讲究：要输出一个**真的能照着做**的合并序列，
//   必须先输出两个子区间内部的合并、最后才输出这一次（后序遍历）。
//   反过来先输出自己，得到的序列是没法执行的 —— 那两堆当时还没并起来呢。
//   这正好又是第 1 章「递归的归」那件事。
//
// 输出的每一行都是一次真实的合并，check:viz 会**照着做一遍**：
// 维护当前这一排堆，逐行检查「这两段确实是当前相邻的两堆」，
// 并把代价累加起来和第一行的答案对照 —— 不只比最终答案，连方案本身也验。
//
// 用法：./path            （用正文那组默认数据 4 1 2 3 5）
//       ./path < 数据文件（格式同 brute.cpp）

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

int n;
vector<long long> s;
vector<vector<long long>> f;
vector<vector<int>> from;

struct Merge { int l, k, r; long long cost; };
vector<Merge> plan;

// 后序：先把左右两段各自合好，最后才轮到这一次合并
void back(int l, int r) {
    if (l == r) return;
    int k = from[l][r];
    back(l, k);
    back(k + 1, r);
    plan.push_back({l, k, r, s[r] - s[l - 1]});
}

int main() {
    // ⚠ cout 和 printf 混用，所以不能关 ios::sync_with_stdio（关了输出顺序会乱）
    vector<long long> a;
    if (cin >> n && n > 0) {
        a.resize(n);
        for (auto& x : a) cin >> x;
    } else {
        a = {4, 1, 2, 3, 5};                            // 正文默认数据
        n = (int)a.size();
    }

    s.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];

    f.assign(n + 2, vector<long long>(n + 2, 0));
    from.assign(n + 2, vector<int>(n + 2, 0));

    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            long long best = LLONG_MAX;
            int bk = l;
            for (int k = l; k < r; k++)
                if (f[l][k] + f[k + 1][r] < best) { best = f[l][k] + f[k + 1][r]; bk = k; }
            f[l][r] = best + s[r] - s[l - 1];
            from[l][r] = bk;                            // ← 全部的额外开销就是这一行
        }

    back(1, n);

    cout << "最小总代价 = " << f[1][n] << "\n\n";
    // ⚠ 表头的空格是手数的：setw 数字节，一个汉字 3 字节只占 2 格宽（第 25 章踩过）
    cout << "  第几次   合并的两段        代价   合并后这一排\n";
    cout << "  ------   ---------------   ----   ------------------------\n";

    vector<long long> cur = a;                          // 跟着方案真的合一遍，打印过程
    vector<int> left(n);                                // cur[i] 现在代表原来的哪一段
    for (int i = 0; i < n; i++) left[i] = i + 1;

    long long acc = 0;
    for (size_t t = 0; t < plan.size(); t++) {
        const auto& m = plan[t];
        size_t i = 0;
        while (i < left.size() && left[i] != m.l) i++;   // 找到左段所在的位置
        cur[i] += cur[i + 1];
        cur.erase(cur.begin() + i + 1);
        left.erase(left.begin() + i + 1);
        acc += m.cost;

        string seg = "[" + to_string(m.l) + "," + to_string(m.k) + "] + ["
                   + to_string(m.k + 1) + "," + to_string(m.r) + "]";
        string row;
        for (size_t q = 0; q < cur.size(); q++) row += (q ? " " : "") + to_string(cur[q]);
        printf("  %6zu   %-15s   %4lld   %s\n", t + 1, seg.c_str(), m.cost, row.c_str());
    }

    cout << "\n  累计代价 " << acc << "，和上面那个答案对得上。\n";
    cout << "  from[l][r] 只多花了一张同样大小的表 —— 这就是第 23 章说的「要方案就得开二维表」。\n";
    return 0;
}

// 石子合并 —— 正解：区间 DP，★ 按区间长度从小到大填
//
// 状态：f[l][r] = 把第 l 堆到第 r 堆合并成一堆，最少要付多少代价。
// 转移：枚举**最后一次**合并的断点 k（左边 [l,k] 已经并成一堆、右边 [k+1,r] 也并成一堆）：
//
//       f[l][r] = min over k in [l, r-1] of ( f[l][k] + f[k+1][r] ) + (a[l] + … + a[r])
//
//   后面那一项和 k 无关 —— 不管怎么分，最后那一次合并总是把整段并成一堆，
//   代价恒等于这一段石子的总数。所以它可以提到 min 外面（第 6 章的前缀和 O(1) 求出来）。
//
// ★ 关键一步：**填表顺序按区间长度从小到大。**
//   因为 f[l][r] 要读 f[l][k] 和 f[k+1][r]，这两个区间都比 [l,r] **短**。
//   「依赖谁，就先填谁」（第 21 章）—— 短的先算好，长的才有得读。
//
//   ⚠ 注意这不是「从左到右」也不是「从右到左」：
//     l 从小到大、r 从小到大地填，f[k+1][r] 那一项就还没算（wrongOrder.cpp 演示了后果）。
//     而 l 从**大**到小、r 从小到大是**对的**（lrOrder.cpp）——
//     长度枚举只是「让依赖先算好」的一种实现方式，不是唯一的那一种。
//
// 复杂度 O(n³)、空间 O(n²)。n = 100 时约 100 万次转移，眨眼就跑完。
// 输入输出同 brute.cpp。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<long long> s(n + 1, 0);                  // 前缀和，1 基下标
    for (int i = 1; i <= n; i++) { long long x; cin >> x; s[i] = s[i - 1] + x; }

    vector<vector<long long>> f(n + 2, vector<long long>(n + 2, 0));
    // 长度为 1 的区间不用合并，代价 0 —— f 初值就是 0，所以不用另写一句

    for (int len = 2; len <= n; len++)              // ★ ① 先枚举区间长度，从短到长
        for (int l = 1; l + len - 1 <= n; l++) {    //   ② 再枚举左端点
            int r = l + len - 1;
            long long best = LLONG_MAX;
            for (int k = l; k < r; k++)             //   ③ 最后枚举断点
                best = min(best, f[l][k] + f[k + 1][r]);
            f[l][r] = best + s[r] - s[l - 1];       // 最后一次合并的代价：整段石子之和
        }

    cout << f[1][n] << "\n";
    return 0;
}