$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

动规 最讨厌了！！！
这道题首先设 $f_{i,j}$ 为从编号 $i$ 到编号 $j$ 这段区间的石子合并的最小代价。
例如：$f_{1,4}$ 只能从以下的3种情况转移而来：

$f_{1,1}+f_{2,4}$
$f_{1,2}+f_{3,4}$
$f_{1,3}+f_{4,4}$

于是我们很容易就能想到：

for (int i = 1;i <= n; i++)
    for (int j = 1;j <= n; j++)
        blablabla...... //更新 f[i][j]

那不就能 AC 了吗？

但是：

$f_{1,4}$ 要由三种情况转移而来。
第一层循环推出 $f_{1,1}$，$f_{1,2}$，$f_{1,3}$ 和 $f_{1,4}$。
再来看 $f_{1,4}$ 的三个递推式……

$f_{1,1}+f_{2,4}$，$f_{1,2}+f_{3,4}$，$f_{1,3}+f_{4,4}$

$f_{2,4}$，$f_{3,4}$，$f_{4,4}$ 都还没算出来！

怎么办呢，从小到大枚举区间长度即可。
另外观察到合并两堆盒子代价相当于原本一段区间石头的重量和，所以前缀和维护。

于是就得到了如下代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 315;
int n, a[N], s[N];
int f[N][N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];
    memset(f, 0x3f3f3f3f, sizeof f);
    for (int i = 1; i <= n; i++) f[i][i] = 0;
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int l = i; l < j; l++)
                f[i][j] = min(f[i][j], f[i][l] + f[l + 1][j] + s[j] - s[i - 1]);
        }
    }
    printf("%d\n", f[1][n]);
    return 0;
}