算法

(区间dp) $O(n^2)$

一堆石子最后一步是将两堆石子合二为一，权值等于砌成两堆石子各自的权值 加上 把两堆石子堆在一起的权值（即总数），举个例子，2 3 5 2，最优解的最后一步是将5(2+3) 和7(5+2)，两堆石子放在一起，把这两堆石子堆在一起是需要5+7的，总和就是2+3+5+2+7
而把两堆石子堆在一起的权值是确定的（7是确定的，是所有石子的总和），不确定的是构成这两堆石子各种的权值（即5和7）
所以最终答案的最优解是需要最后构成两堆石子的权值最小，而构成其中一堆石子的权值最小，也是需要更小最优解的

解题思路，枚举从2到n的每一种区间，将每个区间划分为两部分，动态划分最优解

C++ 代码

#include<iostream>

using namespace std;

const int N=310;

int s[N];
int f[N][N];
int n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&s[i]);

    for(int i=2;i<=n;i++) s[i]+=s[i-1];

    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int l=i,r=i+len-1;
            f[l][r]=1e8;
            for(int j=l;j<r;j++){
                f[l][r]=min(f[l][r],f[l][j]+f[j+1][r]+s[r]-s[l-1]);
            }
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}