题目描述
设有 $N$ 堆石子排成一排,其编号为 $1,2,3,…,N。$
每堆石子有一定的质量,可以用一个整数来描述,现在要将这 $N$ 堆石子合并成为一堆。
每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。
问题是:找出一种合理的方法,使总的代价最小,输出最小代价。
分析
状态表示:f[i][j]表示将i - j这一堆石子合并的所有方案的集合
属性:Min
状态计算:
将集合划分成:
k ∈[l,r)
将石子划分成$i 到 k$ 和 $k 到 1-j$两堆进行合并
状态转移方程为:
f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + (s[r] - s[k] + s[k] - s[l - 1]));
区间DP
通常对于区间DP问题,我们都采用先枚举区间长度,再枚举区间左端点的方式
并且一般 len = 1 时用来初始化,枚举从 len = 2 开始
右端点可以通过r = l + len - 1 来计算,模板如下:
for (int len = 1; len <= n; len++) { // 区间长度
for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
int j = i + len - 1; // 区间终点
if (len == 1) {
dp[i][j] = 初始值
continue;
}
for (int k = i; k < j; k++) { // 枚举分割点,构造状态转移方程
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
}
}
}
模板参考自白马金羁侠少年
C++ Code
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int q[N],s[N],f[N][N]; // f[i][j] 代表将i - j这一堆石子合并的方案的集合
int n;
int main()
{
cin >> n;
// 预处理前缀和
for(int i = 1; i <= n ; ++i){
cin >> q[i];
s[i] = s[i - 1] + q[i];
}
// 区间dp: 先枚举左端点,再枚举区间长度
for(int len = 2; len <= n; ++len){
for(int l = 1; l + len - 1 <= n ; ++l){
int r = l + len - 1;
f[l][r] = 1e8;
for(int k = l; k < r; ++k){
f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + (s[r] - s[k] + s[k] - s[l - 1]));
}
}
}
cout << f[1][n] << endl;
return 0;
}