任意合并问题
例题：洛谷 P1090
问题描述
有 堆石子排成一排，每堆石子质量为
。现需将这些石子合并为一堆，每次可任意选择两堆合并，代价为两堆石子质量之和。要求找出使总代价最小的合并方案，并输出最小代价。
解法分析
贪心策略：每次选择质量最小的两堆石子进行合并
理论依据：
- 二叉树模型：最优合并过程可表示为一棵二叉树，总代价等于各石子质量乘以其深度之和
- 深度特性：最小的两堆石子应位于最优方案的最深层（可通过反证法证明）
- 等价替换：同层叶子节点交换不影响总代价，因此可将最小两堆调整至最深层合并
- 递归应用：合并最小两堆后问题规模减1，可递归应用相同策略
代码实现
#include <cstdio>
#include <queue>
using std::priority_queue;
using std::greater;
using std::vector;
int n, ans = 0;
priority_queue<int, vector<int>, greater<int>> q;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
q.push(x);
}
while (q.size() > 1) {
int x = q.top(); q.pop();
int y = q.top(); q.pop();
ans += x + y;
q.push(x + y);
}
printf("%d\n", ans);
return 0;
}
对于无限制条件的合并问题，贪心算法能够保证获得最优解。
相邻合并问题（链式结构）
例题：洛谷 P1775
问题描述
堆石子排成一行，每堆质量为
。每次只能合并相邻两堆，合并代价为两堆石子质量之和，合并后的新堆与原来相邻的石子保持相邻。要求找出使总代价最小的合并方案。
解法分析
贪心策略的局限性：
考虑以下测试数据：
5
2 9 5 10 6
若采用贪心策略（每次合并最小两堆）：
- 第一步：2+9=11 → [11,5,10,6]，代价11
- 第二步：5+10=15 → [11,15,6]，代价15
- 第三步：6+15=21 → [11,21]，代价21
- 第四步：11+21=32 → [32]，代价32
- 总代价：11+15+21+32=79
更优的合并方案：
- 第一步：2+9=11 → [11,9,10,6]，代价11
- 第二步：5+11=16 → [16,10,6]，代价16
- 第三步：10+6=16 → [16,16]，代价16
- 第四步：16+16=32 → [32]，代价32
- 总代价：11+16+16+32=75
可见贪心策略无法保证获得最优解，因此需采用动态规划方法。
动态规划解法：
定义状态：dp[i][j] 表示合并区间 [i,j] 内石子的最小代价
状态转移方程：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i...j]), 其中 i ≤ k < j
合并代价通过前缀和数组高效计算。
代码实现
#include<bits/stdc++.h>
using namespace std;
int dp[310][310], a[310], n, sum[310];
int main() {
cin >> n;
memset(dp, 0x3f, sizeof(dp)); // 初始化为极大值
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
dp[i][i] = 0; // 单堆石子合并代价为0
}
for (int len = 2; len <= n; len++) { // 枚举区间长度
for (int i = 1; i <= n - len + 1; i++) { // 枚举区间起点
int j = i + len - 1; // 区间终点
for (int k = i; k < j; k++) { // 枚举分割点
dp[i][j] = min(dp[i][j],
dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
}
}
}
cout << dp[1][n];
return 0;
}
相邻合并问题（环式结构）
问题描述
堆石子排成一个环，每堆质量为
。每次只能合并相邻两堆，合并代价为两堆石子质量之和，合并后的新堆与原来相邻的石子保持相邻。要求找出使总代价最小的合并方案。
贪心策略的局限性：
考虑以下测试数据：
8
2 1 1 2 1 7 10 2
若采用贪心策略（每次合并最小两堆）：
- 第一步：1+1=2 → [2,2,2,1,7,10,2]，代价2
- 第二步：2+1=3 → [2,2,3,7,10,2]，代价3
- 第三步：2+2=4 → [4,3,7,10,2]，代价4
- 第四步：4+2=6 → [6,3,7,10]，代价6
- 第五步：6+3=9 → [9,7,10]，代价9
- 第六步：9+7=16 → [16,10]，代价16
- 第七步：16+10=26 → [26]，代价26
- 总代价：2+3+4+6+9+16+26=66
更优的合并方案：
- 第一步：2+1=3 → [2,1,1,3,7,10,2]，代价3
- 第二步：1+1=2 → [2,2,3,7,10,2]，代价2
- 第三步：2+3=5 → [2,5,7,10,2]，代价5
- 第四步：2+2=4 → [4,5,7,10]，代价4
- 第五步：4+5=9 → [9,7,10]，代价9
- 第六步：9+7=16 → [16,10]，代价16
- 第七步：16+10=26 → [26]，代价26
- 总代价：3+2+5+4+9+16+26=65
可见贪心策略无法保证获得最优解，因此需采用动态规划方法。
动态规划解法：
破环成链技巧：将环形问题转化为长度为 的链式问题
定义状态：dp[i][j] 表示合并区间 [i,j] 内石子的最小代价
状态转移方程：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i...j]), 其中 i ≤ k < j
合并代价通过前缀和数组高效计算。
代码实现
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> m(N + 1); // 修正：大小为N+1，索引从1到N
for (int i = 1; i <= N; i++) {
cin >> m[i];
}
// 破环成链
vector<int> a(2 * N + 1);
for (int i = 1; i <= N; i++) {
a[i] = m[i];
a[i + N] = m[i];
}
// 前缀和
vector<int> sum(2 * N + 1, 0);
for (int i = 1; i <= 2 * N; i++) {
sum[i] = sum[i - 1] + a[i];
}
// DP 数组 - 初始化为INT_MAX
vector<vector<int>> dp(2 * N + 1, vector<int>(2 * N + 1, INT_MAX));
// 初始化：单个石堆的合并代价为0
for (int i = 1; i <= 2 * N; i++) {
dp[i][i] = 0;
}
// 区间 DP - 修正：len从2到N（不是2到N）
for (int len = 2; len <= N; len++) { // 合并的堆数
for (int i = 1; i <= 2 * N - len + 1; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1]);
// if(dp[i][j] == dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1]){
// cout << "(" << i << ',' << j << ')' <<"=" << dp[i][j] << " " << " <- " << "(" << i << ',' << k << ')' << "(" << k+1 << ',' << j << ')' << endl;
// }
}
}
}
// 找环形最优 - 修正：start从1开始
int ans = INT_MAX;
for (int start = 1; start <= N; start++) {
ans = min(ans, dp[start][start + N - 1]);
}
cout << ans << endl;
return 0;
}
京公网安备 11010502036488号