3060: 合并石子 前缀和&DP

解题思路:前缀和&DP， f[l][r]表示从i堆到j堆合并的最小得分，i 用来遍历 l,r 之间长度， j确定区间的左边界 

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int f[N][N],s[N];
int main()
{
	int n, l, r;
	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 i = 2; i <= n; i ++)
		for(int j = 1; j - i + 1 <= n; j ++){
			l = j, r = j + i - 1;
			f[l][r] = 1e9;
			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];
	return 0;
}