CSP-S 提高级题解
🎨 视觉封面【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1880 [NOI1995] 石子合并
在环形序列合并优化中,相邻堆合并的顺序直接决定了中间产物与累加得分的演化。洛谷 P1880「[NOI1995] 石子合并」作为全国青少年信息学奥林匹克竞赛(NOI)经典里程碑题,同时也是 CCF GESP 七级考纲(区间动态规划、环形结构破环成链、最值优化)与 CSP-S 组必考的经典区间 DP 原型。与贪心算法(如哈夫曼树模型、合并果子)允许任意两堆合并不同,本题严格限制“每次只能选相邻的两堆合并”,导致贪心选择不具备无后效性,必须通过全局状态枚举进行最优子结构递推。此外,操场为“圆形”闭环结构,首尾相连。常规线性区间 DP 无法直接处理跨越首尾的环形合并。通过将长度为 的环形链条展开复制为长度为 的线性链(“破环成链”思想),配合前缀和数组在 时间内快速计算任意区间合并代价,并按照区间长度从 到 严格升序进行状态转移,即可在 复杂度内同时求得全局最小合并得分与最大合并得分。题目洛谷官方难度评级为普及+/提高。
luogu-P1880 [NOI1995] 石子合并
🔗 洛谷原题传送门:luogu-P1880 [NOI1995] 石子合并
题目描述
在一个圆形操场的四周摆放 堆石子,现要将石子有次序地合并成一堆,规定每次只能选相邻的 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
试设计出一个算法,计算出将 堆石子合并成 堆的最小得分和最大得分。
输入格式
数据的第 行是正整数 ,表示有 堆石子。
第 行有 个整数,第 个整数 表示第 堆石子的个数。
输出格式
输出共 行,第 行为最小得分,第 行为最大得分。
样例 #1
样例输入 #1
4
4 5 9 4样例输出 #1
43
54提示
,。
题目深度剖析
1. 贪心策略为何失效?(对比哈夫曼树与合并果子)
许多初学者在接触石子合并问题时,容易联想到经典贪心题目「合并果子」(洛谷 P1090 / Huffman 树模型):每次从优先队列中取出石子数最小的两堆进行合并,直到只剩一堆。然而,这种贪心策略在石子合并中是完全错误的。
- 根本区别在于空间拓扑约束:
- 在「合并果子」中,任意两堆果子都可以自由合并,空间结构是自由集合,贪心选择具有拟阵性质和完全无后效性;
- 在「石子合并」中,题目明确规定**“每次只能选相邻的 2 堆合并”**。相邻性的强约束破坏了局部贪心的无后效性。
- 反例演示:
设石子堆数量为 (线性排布):
- 贪心策略:首先合并中间两个最小的 (得分 2),序列变为 ;接着合并 (得分 8),序列变为 ;最后合并 (得分 14)。总得分 。
- 最优策略:若先合并左侧 (得分 7),右侧 (得分 7),最后合并 (得分 14)。总得分 。
- 再看另一组:若序列为 ,局部贪心合并极易导致边缘大数被多次重复计入,最终劣于全局统筹规划。因此,本题必须采用**区间动态规划(Interval DP)**穷举分割点。
2. 环形结构的数学映射:破环成链(断环为链)
题目设定操场为“圆形四周摆放”,即第 堆与第 堆亦属于相邻堆。环形结构给线性数组的下标索引带来了周期性跨越的挑战。
- 朴素做法的缺陷:若枚举切开环的位置(共有 种不同的断开方式),每次重新跑一遍 的线性区间 DP,总时间复杂度将上升至 。对于 , 次运算,在 1 秒时限内较为勉强。
- 破环成链(断环为链)经典技巧: 将长度为 的原序列直接复制一份追加到末尾,形成一个长度为 的线性数组: 对于任意一个长度为 的连续子区间 (其中 ),它都恰好对应了在原环形结构中从第 堆开始顺时针遍历整整一圈的某种线性展开! 因此,我们只需在长度为 的数组上执行一次标准的区间 DP,最后在所有长度为 的合法区间 中取极值: 这样只需耗费常数略大的 时间即可一次性搞定所有环形断点。
3. 区间动态规划(Interval DP)的状态设计与转移方程
区间 DP 的核心特征是:以“区间长度”作为动态规划的递推阶段,从小区间的最优解逐步推导出大区间的最优解。
-
前缀和数组优化: 任意连续子区间 内的所有石子总数可以通过前缀和在 时间内求得: 无论这两堆石子内部是按什么顺序合并的,当它们最终合并为 这一整堆时,最后一步产生的合并得分必然等于该区间内所有石子的数量之和 。
-
状态定义:
- :将下标从 到 的石子堆合并成一堆所能获得的最小得分;
- :将下标从 到 的石子堆合并成一堆所能获得的最大得分。
-
边界与基础条件: 当区间长度为 (即 )时,本身就是一堆石子,无需发生任何合并操作,得分恒为 : 其余非对角线状态, 赋极大值(如 ), 赋 或 。
-
状态转移方程: 对于区间 (长度 ),最后一次合并必然发生在某个分割点 ()处,将左半段 与右半段 两大堆合并为最终一堆:
4. 循环阶段次序:为什么必须按照“区间长度”外层循环?
在区间 DP 中,循环层级的顺序是决定算法正确性的生命线。
- 常见错误:外层枚举起点 ,内层枚举终点 。当计算 时,需要用到子问题 。但若采用 正向循环,当处理当前行 时,行号更大的 ()在后续外层迭代中可能根本没有计算完,直接违反了动态规划的无后效性与拓扑有序性。
- 标准写法:
- 最外层循环:枚举区间长度 ,从 递增到 ;
- 第二层循环:枚举区间左端点 ,计算右端点 (需满足 );
- 最内层循环:枚举分割点 ,从 遍历至 。 由于任何子区间 和 的长度都严格小于 ,它们在之前的 阶段中已经全部求解完毕,能够安全无误地参与状态转移。
5. 复杂度剖析与运行指标
- 时间复杂度:
- 数组倍长后规模为 ;
- 外层长度循环 ,共 次;
- 中层起点循环 约 次;
- 内层分割点 循环 次;
- 总运算次数为: 对于 , 次循环操作,在现代评测机上仅需 ,远远低于 的时限要求。
- 空间复杂度:
- 状态矩阵大小为 ;
- 存储 、 两个整型二维数组仅需 ,对内存的消耗微乎其微。
6. 核心考点与竞赛避坑指南
- 破环成链的外层长度上限: 虽然数组长度扩展至 ,但由于我们最终只需要合并 堆石子,外层循环的区间长度 只需枚举到 即可,无需枚举到 。这直接节约了一半的常数时间开销。
- 单堆特判( 的边界): 当 时,无需进行任何合并操作,最小得分与最大得分均为 。代码中外层循环 从 2 开始,对于 循环直接不执行,最终答案统计取得 ,天然契合单点边界。
- 极值初始化的正确范围:
最小得分 的初始值不可过大导致加法溢出(如使用
INT_MAX与前缀和相加可能发生整型上溢),设定为1e9既足够大又绝对安全。
完整参考代码(C++11 规范)
/**
* 题目: 【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1880 [NOI1995] 石子合并
* 题号: P1880
* 归属: GESP七级 / CSP-S / 区间动态规划经典题
* 博客: https://www.coderli.com/gesp-7-luogu-p1880/
* 标准: C++11 (严格遵循 CCF GESP 官方规范)
*/
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
// 最大石子堆数常量定义
// 题目中 N <= 100,破环成链复制后最大长度为 2N = 200
const int MAXN = 205;
const int INF = 1e9; // 极大值常量,用于最小值得分初始化
// a 数组存储石子数量,prefix_sum 存储前缀和
int a[MAXN];
int prefix_sum[MAXN];
// dp_min[i][j]: 将区间 [i, j] 内的石子合并成一堆的最小得分
// dp_max[i][j]: 将区间 [i, j] 内的石子合并成一堆的最大得分
int dp_min[MAXN][MAXN];
int dp_max[MAXN][MAXN];
int main() {
int n;
cin >> n;
// 读入原始 n 堆石子的数量,并将序列复制一份扩展到 2n,完成环形破环成链
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i + n] = a[i];
}
// 计算扩展后长度为 2n 的前缀和数组
prefix_sum[0] = 0;
for (int i = 1; i <= 2 * n; ++i) {
prefix_sum[i] = prefix_sum[i - 1] + a[i];
}
// 初始化 DP 状态矩阵
// 单堆石子(i == j)无需合并,得分为 0;其余状态赋初始极值
for (int i = 1; i <= 2 * n; ++i) {
for (int j = 1; j <= 2 * n; ++j) {
if (i == j) {
dp_min[i][j] = 0;
dp_max[i][j] = 0;
} else {
dp_min[i][j] = INF;
dp_max[i][j] = -1;
}
}
}
// 区间 DP 阶段递推:外层枚举合并区间的长度 len,从 2 递增至 n
for (int len = 2; len <= n; ++len) {
// 枚举区间的左端点 i,保证右端点 j 在合法范围 2n 之内
for (int i = 1; i + len - 1 <= 2 * n; ++i) {
int j = i + len - 1; // 当前区间的右端点
int sum_val = prefix_sum[j] - prefix_sum[i - 1]; // 合并该区间产生的固定累计得分
// 枚举最后一次合并的分割点 k,将区间分为 [i, k] 与 [k + 1, j] 两部分
for (int k = i; k < j; ++k) {
dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum_val);
dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum_val);
}
}
}
// 遍历所有可能的环形起点 i (1 <= i <= n),统计长度为 n 的闭区间合并极值
int ans_min = INF;
int ans_max = -1;
for (int i = 1; i <= n; ++i) {
ans_min = min(ans_min, dp_min[i][i + n - 1]);
ans_max = max(ans_max, dp_max[i][i + n - 1]);
}
// 按题目要求输出两行结果:第一行最小得分,第二行最大得分
cout << ans_min << endl;
cout << ans_max << endl;
return 0;
}所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1113 [USACO02FEB] 杂务
生活与工业生产中的工序流水线调度,天然蕴含着严苛的时序依赖:地基未筑不可起高楼,原料未至不可开炉灶。洛谷 P1113「[USACO02FEB] 杂务」以牧场日常作业为背景,生动抽象出工程管理与图论中的核心模型——有向无环图(DAG)的关键路径与最早完成时间计算(Crit...
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3371 【模板】单源最短路径(弱化版)
在交通网络寻径、物流供应链调度与通信路由协议中,求解从指定始发枢纽到网络中所有连通节点的最优开销,是离散优化与图论的核心基石。洛谷 P3371「【模板】单源最短路径(弱化版)」给出了非负权有向图单源最短路径(Single-Source Shortest Path, SS...
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3366 【模板】最小生成树
在通信基站管网布线、电力网架设以及交通枢纽规划等重大工程中,如何在保证所有节点相互连通的前提下,使铺设线路的总建设开销(边权之和)达到全局最小,是经典的最小生成树(Minimum Spanning Tree, MST)离散优化问题。洛谷 P3366「【模板】最小生成树」...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

