洛谷 P1775 石子合并（弱化版）

// P1775 石子合并（弱化版）—— ★ 这一版就能 AC。
//
// ★★ 先说清楚这一页的位置：**这道题就是[第 26 章正文](/ch/26-interval-dp/)
//   那道题的原题**（直线版、只求最小值）。所以下面这份代码和正文的 `fast.cpp`
//   **是同一个算法、同一份写法**，一个字都不用改：
//
//       f[l][r] = min over k in [l, r-1] of ( f[l][k] + f[k+1][r] ) + (a[l] + … + a[r])
//       ① 先枚举区间长度（从短到长）② 再枚举左端点 ③ 最后枚举断点
//
// ⇒ 题单那句「写完直接交，一遍就该过」是真的。
//   ⚠ 而这一页要问的是另外三件事，**没有一件在 DP 上**：
//   ① 「只能合并**相邻**两堆」这五个字值多少（去掉它就是[合并果子](/sol/p1090/)）；
//   ② 少写一个前缀和会贵多少（⚠ 我的草稿在这儿猜错了）；
//   ③ 顶格答案有多大 —— 要不要 `long long`。
//
// 规模：`N ≤ 300` ⇒ 转移 `n(n²−1)/6` = **4 499 950** 次，眨眼就跑完。

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

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

    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 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];       // 最后一次合并：整段之和
        }
    printf("%lld\n", f[1][n]);
    return 0;
}

// P1775：区间 DP 写对了，但**区间和是每次现算的** —— 它是对的，只是慢一个量级。
//
// 正解那一行 `f[l][r] = best + s[r] - s[l-1]` 用的是第 6 章的前缀和，`O(1)`。
// 这一版把它换成一个 `for` 循环现加一遍。
//
// ⚠⚠ 我的草稿在这儿写的是「复杂度从 `O(n³)` 掉到 `O(n⁴)`」—— **实测把它打回来了**：
//   区间只有 `O(n²)` 个，而这一句是**每个区间只算一次**，
//   所以它加起来是 `Σ len ≈ n³/6` —— 和 DP 的转移次数**同一个量级**。
//   顶格 `n = 300`：转移 4 499 950 次，这一版多做 4 544 800 次加法 —— **只贵 1.0 倍**。
//
// ★ 真要掉一个量级，得把它写进**最里面那层 `k` 循环**里（那才是 `O(n⁴)`，
//   顶格约 3.4 亿次）。⇒ **「少写一个前缀和」值多少，取决于你把它少写在哪一层。**
//
// ⚠ 它答案永远是对的 ⇒ **对拍一万轮也发现不了**（[P5019](/sol/p5019/) 那条：
//   样例和对拍筛的都是「答案错」，对「答案对但跑不完」完全无能为力）。

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

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) if (scanf("%lld", &a[i]) != 1) return 0;

    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 best = LLONG_MAX;
            for (int k = l; k < r; k++) best = min(best, f[l][k] + f[k + 1][r]);
            long long sum = 0;
            for (int i = l; i <= r; i++) sum += a[i];      // ✗ 每次现加一遍：多出来的那一层
            f[l][r] = best + sum;
        }
    printf("%lld\n", f[1][n]);
    return 0;
}