石子合并 - 区间动态规划

题意

设有 \(N\) 堆石子排成一排，其编号为 \(1 \sim N\)。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 \(N\) 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

找出一种合理的方法，使总的代价最小，输出最小代价。

样例输入输出

4
1 3 5 2

算法

区间动态规划 (区间DP)

\(\to\) OI-Wiki

在区间DP中，我们设置的状态有了新的含义。例如 \(f_{i, j}\) 表示 \(i\) 到 \(j\) 这一段区间内的某种属性。

一般地，最终的求解答案为 \(f_{1, n}\)。

解题思路

1. 确定状态

我们以 \(f_{i, j}\) 表示 \(i\) 到 \(j\) 这一段区间内合并石子的最小代价。

2. 划分阶段 & 决策选择

首先，如果合并 \(l\) 到 \(r\) 这一段区间，那么需要先把这一段区间的石子总数算出来。这里求区间和可以用到前缀和算法，求解 \(l\) 到 \(r\) 这一段区间仅需要 \(s_r - s_{l-1}\)。

由于总会有最后一步的合并过程，那么我们就对合并过程进行分类讨论。

首先，找到一个分界点 \(k\)。这个分界点指的是如果要把 \(l\) 到 \(r\) 这一段区间合并，最后一次合并的两部分的分界点。其中第一部分为 \(l \sim k\)，第二部分为 \(k+1 \sim r\)。

我们按照区间的长度进行求解，也就是先求最段的区间，再求长的区间。因此，再求 \(l\) 到 \(r\) 区间的时候，我们认为刚才分的两段区间都已经求解完毕。

因此我们只需要找到这个 \(k\)，使得 \(f_{l, k} + f_{k+1, r} + 区间和\) 的值最小即可。

3. 边界条件

如果区间长的为 \(1\)，那么就不需要合并，总代价为 \(0\)。

4. 求解目标

最终我们要求 \(1\) 到 \(N\) 这一段区间的最小代价，因此答案为 \(f_{1, N}\)。

代码

#include <iostream>

using namespace std;

const int N = 310, INF = 0x3f3f3f3f;

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

int main(){
	// 读入并预处理前缀和 
	scanf("%d", &n);
	
	for(int i=1; i<=n; i++){
		scanf("%d", s+i);
		s[i] += s[i-1];
	}
	
	// 边界条件，长度为 1 代价为 0 
	for(int i=1; i<=n; i++){
		f[i][i] = 0;
	}
	
	// 求解 f[i][j] 
	for(int len=2; len<=n; len++){		// 外层枚举长度 
		for(int i=1; i+len-1<=n; i++){	// 中层枚举起点 
			int l = i, r = i + len - 1;	// 找到 l 和 r 
			f[l][r] = INF;				// 初始化为最大值 
			for(int k=l; k<r; k++){		// 内层枚举分界点 
			
								//	    前一部分    后一部分       区间和 
				f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1]);
			}
		}
	}
	
	// 答案为 f[1][n] 
	cout << f[1][n];
	return 0;
}