石子合并

题目链接：https://www.acwing.com/problem/content/description/284/

题目描述

设有 N 堆石子排成一排，其编号为 1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 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。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入描述

第一行一个数 N 表示石子的堆数 N。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。

输出描述

输出一个整数，表示最小代价。
1≤N≤300

示例

输入

4
1 3 5 2

输出

22

分析

约定

记第i堆石子的质量为w[i]。
为后续解题做准备，记前i堆石子的质量和为s[i]。

状态表示

f(i,j)表示合并第i堆到第j堆石子的最小代价。

状态划分与计算

对于[i,j]这样一个区间，该区间合并的最后一步必是两个子区间的合并。
两个子区间合并的代价必然为s[j]-s[i-1]，与是哪两个子区间无关。(此处使用前缀和优化时间)
因此，求解f(i,j)就只需要枚举每一种双子区间划分方案，取最小代价和加上s[j]-s[i-1]即可。

状态转移方程

由上一步的分析，我们得到状态转移方程如下：
f(i,j)=min(f(i,k)+f(k+1,j)+s[j]-s[i])     (k=i,i+1,···,j-1)
k对于[i,j]是左闭右开的，以每一种划分前面那个元素的序号代表该种划分，不一定非要这样，保持一致，能遍历所有划分都可。

AC代码

---

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int N = 301;

int n;
int s[N];
int f[N][N];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{

		int temp;
		cin >> temp;
		s[i] = s[i - 1] + temp;
	}
	
	//区间长度为1，表示仅一个元素，合并代价为0，故从2开始
	for (int len = 2; len <= n; len++)	
	{
		for (int i = 1; i + len - 1 <= n; i++)
		{
			int l = i, r = i + len - 1;
			f[l][r] = 1e8;	//记得初始化
			for (int j = i; j < r; j++)
			{
				f[l][r] = min(f[l][r], f[i][j] + f[j + 1][r] + s[r] - s[l - 1]);
			}
		}
	}
	cout << f[1][n] << endl;
	return 0;
}