区间DP

注意，将相邻的果子堆合并，意味着你不能贪心

设f[i][j]代表合并i~j之间堆的最小消耗

不妨从终点考虑问题，即结果为两个子区间合并的最小值再加上合并需要的代价即可。

枚举两个子区间，即枚举这个区间的中间点k，使这个区间被分为[i,k]和[k+1,j]两个区间，取一遍最小值加上合并的即为当前区间所求。

至于合并的代价，用前缀和即可。

#include<bits/stdc++.h>
using namespace std;
int f[305][305],a[305],sum[305];
int main(){
	int n;
	scanf("%d",&n);//输入果子数
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]+=sum[i-1]+a[i];//前缀和加快速度
	}
	for(int l=1;l<=n;l++){//注意，按照合并的堆数循环
		for(int i=1;i<=n-l+1;i++){//小心越界
			int j=l+i-1;//j通过i,l得到
			if(i!=j)f[i][j]=INT_MAX;//设为最大（初始化）
			for(int k=i;k<j;k++){//枚举中间点
				f[i][j]=min(f[i][k]+f[k+1][j]+sum[j]-sum[i-1],f[i][j]);//转移方程
			}
		}
	}
	printf("%d\n",f[1][n]);//输出
	return 0;
}