石子合并

题目描述

输入格式

第一行一个数 $N$ 表示石子的堆数 $N$。

第二行 $N$ 个数，表示每堆石子的质量(均不超过1000)。

输出格式

输出一个整数，表示最小代价。

数据范围

1≤$N$≤300

输入样例：

4
1 3 5 2

输出样例：

22

分析

• 合并的代价其实就是$[i, j]$的价值的总和，所以可以使用前缀和

区间DP一般都是两层循环，外层len，内层起点

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

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

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> s[i], s[i] += s[i - 1];
    
    for (int len = 2; len <= n; len ++ )
        for (int i = 1; i + len - 1<= n; i ++ )
        {
            int j = i + len - 1;
            f[i][j] = 1e8;
            for (int k = i; k < j; k ++ )
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
        }
        
    cout << f[1][n] << endl;
    
    return 0;
}