问题描述
在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
输入格式
输入第一行包含一个整数n，表示石子的堆数。
接下来一行，包含n个整数，按顺序给出每堆石子的大小 。
输出格式
输出一个整数，表示合并的最小花费。
1
2
3
4
5
6
7样例输入
5
1 2 3 4 5
样例输出
33
数据规模和约定
1<=n<=1000, 每堆石子至少1颗，最多10000颗。
四边形不等式
s[i][j]表示dp[i][j]最优解的位置
我们可以证明，s[i,j-1]≤s[i,j]≤s[i+1,j]
那么改变状态转移方程为：
dp[i,j]=min{dp[i,k]+dp[k,j]+w[i][j]}(s[i,j-1]≤k≤s[i+1,j])
w[i][j]=sum[j]-sum[i-1] 表示i到j堆石子数量之和 即以k为分割点合并的代价1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#include<iostream>
#include<cstring>
#define MAX 1010
#define INF 0x3f3f3f
using namespace std;
int cost[MAX],dp[MAX][MAX],sum[MAX],s[MAX][MAX];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>cost[i];
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+cost[i];
for(int v=2;v<=n;v++ ){
for(int i=1;i<=n-v+1;i++)
{
int j=i+v-1;
int k1=(s[i][j-1]>i)?s[i][j-1]:i;
int k2=(s[i+1][j]<j)?s[i+1][j]:j;
dp[i][j]=dp[i][k1]+dp[k1+1][j];
s[i][j]=k1;
for(int k=k1+1;k<=k2;k++){
if(dp[i][j]>dp[i][k]+dp[k+1][j]){
dp[i][j]=dp[i][k]+dp[k+1][j];
s[i][j]=k;
}
}
dp[i][j]+=sum[j]-sum[i-1];
}
}
cout<<dp[1][n];
}