$\LARGE\color{orange}{刷题日记(算法提高课)}$

这是一道典型的区间 DP 问题

我们定义 $f[l][r]$ 表示集合：合并区间 $[l,r]$ 内的所有石子的不同选法，属性为最大值

对于区间 DP 问题，我们先枚举区间长度，后枚举区间左端点

对于同一个区间的所有不同选法而言，我们将区间 $[l,r]$ 分成 $[l,k]$ 和 $[k+1,r]$ 通过枚举 $k$ 来实现对 $f[l][r]$ 进行赋值

这么考虑是因为，这个区间最后一步一定是两个石子进行合并，而这两个石子所需体力各不相同，而导致这一点的正是对这段区间不同的划分，因此我们通过枚举 $k$ 来实现对区间的划分

因此状态转移方程为：

$$ f[l][r]=max(f[l][r],\ f[l][k]+f[k+1][r]+s[l-1][r])\ ,\ 其中 s[i] 为前缀和数组 $$

完整代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 310;
int s[N];
int f[N][N];
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> s[i];
    for(int i = 1; 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] = 0x3f3f3f3f;
            for(int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }

    cout << f[1][n] << endl;

    return 0;
}