Description

在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请设计一个程序，计算出将N堆石子合并成一堆的最小得分。

Input

每组数据第1行为一个正整数N(2<=N<=100)，以下N行，每行一个正整数，小于10000，分别表示第i堆石子的个数(1<=i<=N)。

Output

对于每组数据输出一个正整数，即最小得分

Sample Input

7
13
7
8
16
21
4
18

Sample Output

239

思路

该题设f[i][j]为从i到j的所有石子合并成一堆的最小得分，那么有2种方法可以完成：

1. 先枚举长度，再枚举起点
2. 先枚举起点，再枚举终点
   也可以设f[i][j]为从第i个起，后面的j个数合并的最小代价，然后枚举长度和边界
   我用了第1种：
   f [ i ] [ j ] = m i n ( f [ i ] [ j ] , f [ i ] [ k ] + f [ k + 1 ] [ j ] + 第 1 至 j 的 和 − 第 1 至 i − 1 的 和 ) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+第1至j的和-第1至i-1的和) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+第1至j的和−第1至i−1的和)
   (2<=l<=n,1<=i<=n&&j<=n,j=i+l)

#include<iostream>
#include<algorithm>
using namespace std;
int n,a[300],s[300],dp[300][300];
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
	for (int l=2;l<n;l++) for (int i=1,j=i+l;j<=n&&i<=n;i++,j=i+l)
	{
		dp[i][j]=0x7f7f7f7f;
		for (int k=i;k<j;k++)
		{
			dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
		}
	}
	cout<<dp[1][n];
	return 0;
}

第2种方法也可以：

#include<iostream>
#include<algorithm>
using namespace std;
int n,a[300],s[300],dp[300][300];
int main()
{
 cin>>n;
 for (int i=1;i<=n;i++)
 {
  cin>>a[i];
 }
 for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
 for (int i=n-1;i>=1;i--) for (int j=i+1;j<=n;j++)
 {
  dp[i][j]=0x7f7f7f7f;
  for (int k=i;k<j;k++)
  {
   dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
  }
 }
 cout<<dp[1][n];
 return 0;
}

第3种：
f [ i ] [ j ] = m i n ( f [ i ] [ j ] , f [ i + k ] [ j − k ] + f [ i ] [ k ] + 第 1 至 j + i − 1 的 和 − 第 1 至 i − 1 的 和 ) f[i][j]=min(f[i][j],f[i+k][j-k]+f[i][k]+第1至j+i-1的和-第1至i-1的和) f[i][j]=min(f[i][j],f[i+k][j−k]+f[i][k]+第1至j+i−1的和−第1至i−1的和)
代码：

#include<iostream>
#include<algorithm>
using namespace std;
int n,a[300],s[300],dp[300][300];
int main()
{
 cin>>n;
 for (int i=1;i<=n;i++)
 {
  cin>>a[i];
 }
 for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
 for (int l=1;l<=n;l++) for (int i=1;i<=n;i++)
 {
  dp[i][l]=0x7f7f7f7f;
  for (int k=1;k<l;k++)
  {
   dp[i][l]=min(dp[i][l],dp[i+k][l-k]+dp[i][k]+s[l+i-1]-s[i-1]);
  }
  if (l==1) dp[i][l]=0;
 }
 cout<<dp[1][n];
 return 0;
}