C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 310;
int f[N][N];
int a[N],s[N];
int n;
int main()
{
cin>>n;
for(int i =1; i <= n; i ++)
{
cin>>a[i];
s[i] = s[i-1] + a[i];
}
memset(f, 0x3f, sizeof f);
for(int len = 1; len <= n; len++) //枚举区间长度
{
for(int i =1; i + len -1 <= n; i++) //左端点
{
int j = len + i - 1; //获取右端点
if (len == 1) {
f[i][j] = 0; // 边界初始化
continue;
}
for(int k = i; k <= j-1 ;k++)
{
f[i][j] = min(f[i][j] , f[i][k]+f[k+1][j]+s[j]-s[i-1]);
}
}
}
cout << f[1][n];
return 0;
}
f[i][j]代表的是合成[i][j]这一堆石子的最小代价,所以 f[i][k]+f[k+1][j]+s[j]-s[i-1]等于
合成[i][k]这堆石子的最小代价 + [k+1][j]这堆石子的最小代价 + 两堆石子合成的代价
两堆石子合成的代价就等于[i][j]区间所有石子相加
题目思路:直接划划分区间,求出所有的方案,取最小值,1~4堆,可以划分成12,23,34这是区间为2 ,当区间为3可以划分为12 3,23 4,1 23,2 34,当区间为4时 1 23 4 , 12 3 4, 12 34 ,这几种,
像合成 23区间 123区间这些我们早就已经算出来了,只需要根据获得区间的最小代价+区间的总重量即可