石子合并

描述

有n堆石子排成一行,每次选择相邻的两堆石子,将其合并为一堆,该次合并的消费为两堆石子个数之和。已知每堆石子的石子个数,求当所有石子合并为一堆时,最小的消费。

输入

有多组测试数据,输入到文件结束。
每组测试数据第一行有一个整数n,表示有n堆石子。
接下来的一行有n(0< n <200)个数,分别表示这n堆石子的数目,用空格隔开

输出

输出总代价的最小值,占单独的一行

样例

  • Input
    3
    1 2 3
    7
    13 7 8 16 21 4 18
  • Output
    9
    239

思路

用dp[i][j]表示区间[i,j]的最小花费。(N^2)枚举区间[i,j],用断点k遍历i~j,则dp[i][j]=min(dp[i][k]+dp[k][j]+sum[j]-sum[i-1]),其中sum[i]为i的前缀和。时间复杂度为O(N^3)

Code

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
34
#include<bits/stdc++.h>
#define INIT(a,b) memset(a,b,sizeof(a))
#define LL long long int
using namespace std;
const int MAX=0x7fffffff;
const int MIN=-0x7fffffff;
const int INF=0x3f3f3f3f;
const int Mod=1e9+7;
const int MaxN=1e7+7;
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int n,dp[201][201];
int sum[201],x;
cin>>n;
INIT(sum,0);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
dp[i][j]=INF;
for(int i=1;i<=n;i++){
cin>>x;
sum[i]=sum[i-1]+x;
dp[i][i]=0;
}
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
cout<<dp[1][n]<<endl;
return 0;
}
Donate comment here