一、原题目

1.题目描述

设有N堆沙子排成一排，其编号为1，2，3，…，N（N< =300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将N堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有4堆沙子分别为1 3 5 2我们可以先合并1、2堆，代价为4，得到4 5 2又合并1，2堆，代价为9，得到9 2，再合并得到11，总代价为4+9+11=24，如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。

2.输入

第一行一个数N表示沙子的堆数N。第二行N个数，表示每堆沙子的质量。 a[i]< =1000。

3.输出

输出一个整数，合并的最小代价。

4.样例输入

4
1 3 5 2

5.样例输出

22

二、题目分析

与经典的”矩阵连乘“问题类似，采用动态规划算法。

设 $d p [i] [j]$ 表示把编号为 $i$ 的沙子到编号为 $j$ 的沙子合并所需要的最小代价。易知目标是求出 $d p [1] [n]$ 。

下面给出状态转移方程：

当 $i = j$ 时，合并自身（等价于无操作）不需要任何代价，即
$d p [i] [j] = 0$
当 $i \neq = j$ 时，我们在编号 $i$ 与编号 $j$ 之间插入一个隔板。假设在编号 $k$ 的沙子后插入隔板，那么合并 $i$ 到 $j$ 转换成先把 $i$ 到 $k$ 合并，再把 $k + 1$ 到 $j$ 合并，最后合并刚才得到的两堆沙子。因此 $d p [i] [j]$ 与隔板 $k$ 的插入位置有关，只需从 $k = i$ 到 $j ? 1$ 遍历，找到最小的合并代价即可。即
$d p [i] [j] = d p [i] [k] + d p [k + 1] [j] + S U M (i, j)$
$S U M (i, j)$ 为合并左右两堆沙子的代价，很容易知道，该代价的值为编号 $i$ 到编号 $j$ 沙子的质量求和。

上述过程中，求任意一段区间沙子的质量和可以通过前缀和来减小时间复杂度。记 $p r e S u m [i]$ 为编号 $1$ 至编号 $i$ 的沙子的质量和，则任意区间 $[i, j]$ 沙子的质量和为：
$S U M (i, j) = p r e S u m [j] ? p r e S u m [i ? 1]$

有了状态转移方程，可以很容易的求解 $d p [1] [n]$ 。

三、代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int N;
int preSum[10010];
int dp[10010][10010];

int main()
{
	cin>>N;
	int x;
	preSum[0] = 0;
	for(int i = 1; i <= N; i++){
		cin>>x;
		preSum[i] = preSum[i - 1] + x;
	}
	for(int i = 1; i <= N; i++)
		dp[i][i] = 0;
	for(int r = 1; r <= N; r++){
		int i = 1;
		while(i + r <= N){
			int j = i + r;

			int min = 2000;
			for(int k = i; k <= j - 1; k++){
				int temp = dp[i][k] + dp[k + 1][j] + preSum[j] - preSum[i - 1];
				if(min > temp) min = temp;
			}
			dp[i][j] = min;
			
			i++;
		}
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++)
			cout<<dp[i][j]<<" ";
		cout<<endl;
	}
	cout<<dp[1][N]<<endl;
	return 0;
}