把环断成长度为 n 的所有链段，做区间 DP，同时维护最小合并代价和最大合并代价。
OJ: luogu
题目 ID: P1880
难度:普及+/提高
标签:动态规划区间dp环形处理
日期: 2026-06-21 12:27
题意
有 n 堆石子围成一个环。
每次只能选相邻两堆合并，得分等于这两堆石子数之和。
问把所有石子最终合成一堆时：
- 最小总得分是多少
- 最大总得分是多少
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
const int INF = 0x3f3f3f3f;
int n;
vector<int> stones;
map<vector<int>, pair<int, int> > memo;
// 暴力递归：当前 stones 表示环上剩余的石子堆。
pair<int, int> dfs(vector<int> cur) {
int m = (int) cur.size();
if (m == 1) {
return make_pair(0, 0);
}
map<vector<int>, pair<int, int> >::iterator it = memo.find(cur);
if (it != memo.end()) {
return it->second;
}
int best_min = INF;
int best_max = -INF;
for (int i = 0; i < m; i++) {
int j = (i + 1) % m;
int merged = cur[i] + cur[j];
vector<int> nxt;
nxt.push_back(merged);
// 合并掉 i 和 j 后，剩余元素按环上的相对顺序接在 merged 后面。
for (int step = 1; step <= m - 2; step++) {
int idx = (j + step) % m;
nxt.push_back(cur[idx]);
}
pair<int, int> sub = dfs(nxt);
best_min = min(best_min, sub.first + merged);
best_max = max(best_max, sub.second + merged);
}
pair<int, int> ans = make_pair(best_min, best_max);
memo[cur] = ans;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
stones.resize(n);
for (int i = 0; i < n; i++) {
cin >> stones[i];
}
memo.clear();
pair<int, int> ans = dfs(stones);
cout << ans.first << '\n';
cout << ans.second << '\n';
return 0;
}暴力做法就是递归模拟：
- 当前环上有多少堆石子
- 枚举把哪一对相邻石子合并
- 继续递归
这样可以帮助理解题目，但复杂度是指数级，只能做很小的数据。
这题的标准做法是区间 DP。
如果石子是排成一条链，那么设：
dp_min[l][r]：把区间[l, r]合成一堆的最小代价dp_max[l][r]：把区间[l, r]合成一堆的最大代价
转移时枚举最后一次合并的位置 k：
- 左边先合成一堆
- 右边先合成一堆
- 最后再把这两堆合并
所以有：
dp_min[l][r] = min(dp_min[l][k] + dp_min[k+1][r] + sum(l,r))dp_max[l][r] = max(dp_max[l][k] + dp_max[k+1][r] + sum(l,r))
其中 sum(l,r) 表示区间石子总数，因为最后这一次把两大堆合起来，得分就是整个区间总和。
但原题是一个环，不是链。
处理环形区间 DP 的常见办法是：
- 把数组复制一遍，变成长度
2n - 这样所有“断环成链”的方案，都能对应成一个长度为
n的连续区间 - 枚举每个起点
l，看区间[l, l+n-1]的答案
最后：
- 所有这些长度为
n的区间里，最小值的最小者就是答案 - 最大值的最大者就是答案
DP 转移方程
核心状态：
dp_min[l][r] 与 dp_max[l][r]
核心转移：
dp[l][r]=opt_k(dp[l][k]+dp[k+1][r]+sum(l,r))
答案收束：
长度 n 的所有区间取最小/最大
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
const int INF = 0x3f3f3f3f;
int n;
int a[MAXN];
int sumv[MAXN];
int dp_min[MAXN][MAXN];
int dp_max[MAXN][MAXN];
// 计算区间 [l, r] 的石子总数。
int range_sum(int l, int r) {
return sumv[r] - sumv[l - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i + n] = a[i];
}
for (int i = 1; i <= 2 * n; i++) {
sumv[i] = sumv[i - 1] + a[i];
}
for (int i = 1; i <= 2 * n; i++) {
for (int j = 1; j <= 2 * n; j++) {
dp_min[i][j] = INF;
dp_max[i][j] = -INF;
}
dp_min[i][i] = 0;
dp_max[i][i] = 0;
}
// 区间 DP：先枚举长度，再枚举左端点。
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= 2 * n; l++) {
int r = l + len - 1;
int seg_sum = range_sum(l, r);
for (int k = l; k < r; k++) {
dp_min[l][r] = min(dp_min[l][r], dp_min[l][k] + dp_min[k + 1][r] + seg_sum);
dp_max[l][r] = max(dp_max[l][r], dp_max[l][k] + dp_max[k + 1][r] + seg_sum);
}
}
}
int ans_min = INF;
int ans_max = -INF;
for (int l = 1; l <= n; l++) {
int r = l + n - 1;
ans_min = min(ans_min, dp_min[l][r]);
ans_max = max(ans_max, dp_max[l][r]);
}
cout << ans_min << '\n';
cout << ans_max << '\n';
return 0;
}复杂度
区间 DP 一共有
空间复杂度是
总结
这题是非常典型的“环形区间 DP”。
关键步骤只有两件事：
- 先写好链上的区间 DP
- 再用“复制数组”的方式把环断成链
一旦想清楚最后一次合并一定会把某个区间 [l,r] 的左右两部分拼起来，转移就很自然了。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
