OneCoder Avatar
OneCodercoderli.com · 1025 篇博文
⌘ CSP-S

CSP-S 提高级题解

🎨 视觉封面

【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1880 [NOI1995] 石子合并

📅 2026-10-05·✍️ OneCoder·计算中...·⏱️ 16 分钟

在环形序列合并优化中,相邻堆合并的顺序直接决定了中间产物与累加得分的演化。洛谷 P1880「[NOI1995] 石子合并」作为全国青少年信息学奥林匹克竞赛(NOI)经典里程碑题,同时也是 CCF GESP 七级考纲(区间动态规划、环形结构破环成链、最值优化)与 CSP-S 组必考的经典区间 DP 原型。与贪心算法(如哈夫曼树模型、合并果子)允许任意两堆合并不同,本题严格限制“每次只能选相邻的两堆合并”,导致贪心选择不具备无后效性,必须通过全局状态枚举进行最优子结构递推。此外,操场为“圆形”闭环结构,首尾相连。常规线性区间 DP 无法直接处理跨越首尾的环形合并。通过将长度为 的环形链条展开复制为长度为 的线性链(“破环成链”思想),配合前缀和数组在 时间内快速计算任意区间合并代价,并按照区间长度从 到 严格升序进行状态转移,即可在 复杂度内同时求得全局最小合并得分与最大合并得分。题目洛谷官方难度评级为普及+/提高。

luogu-P1880 [NOI1995] 石子合并

🔗 洛谷原题传送门:luogu-P1880 [NOI1995] 石子合并

题目描述

在一个圆形操场的四周摆放 堆石子,现要将石子有次序地合并成一堆,规定每次只能选相邻的 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。

试设计出一个算法,计算出将 堆石子合并成 堆的最小得分和最大得分。

输入格式

数据的第 行是正整数 ,表示有 堆石子。

第 行有 个整数,第 个整数 表示第 堆石子的个数。

输出格式

输出共 行,第 行为最小得分,第 行为最大得分。

样例 #1

样例输入 #1

Code2 行
4
4 5 9 4

样例输出 #1

Code2 行
43
54

提示

,。


题目深度剖析

1. 贪心策略为何失效?(对比哈夫曼树与合并果子)

许多初学者在接触石子合并问题时,容易联想到经典贪心题目「合并果子」(洛谷 P1090 / Huffman 树模型):每次从优先队列中取出石子数最小的两堆进行合并,直到只剩一堆。然而,这种贪心策略在石子合并中是完全错误的。

  • 根本区别在于空间拓扑约束:
    • 在「合并果子」中,任意两堆果子都可以自由合并,空间结构是自由集合,贪心选择具有拟阵性质和完全无后效性;
    • 在「石子合并」中,题目明确规定**“每次只能选相邻的 2 堆合并”**。相邻性的强约束破坏了局部贪心的无后效性。
  • 反例演示: 设石子堆数量为 (线性排布):
    • 贪心策略:首先合并中间两个最小的 (得分 2),序列变为 ;接着合并 (得分 8),序列变为 ;最后合并 (得分 14)。总得分 。
    • 最优策略:若先合并左侧 (得分 7),右侧 (得分 7),最后合并 (得分 14)。总得分 。
    • 再看另一组:若序列为 ,局部贪心合并极易导致边缘大数被多次重复计入,最终劣于全局统筹规划。因此,本题必须采用**区间动态规划(Interval DP)**穷举分割点。

2. 环形结构的数学映射:破环成链(断环为链)

题目设定操场为“圆形四周摆放”,即第 堆与第 堆亦属于相邻堆。环形结构给线性数组的下标索引带来了周期性跨越的挑战。

  • 朴素做法的缺陷:若枚举切开环的位置(共有 种不同的断开方式),每次重新跑一遍 的线性区间 DP,总时间复杂度将上升至 。对于 , 次运算,在 1 秒时限内较为勉强。
  • 破环成链(断环为链)经典技巧: 将长度为 的原序列直接复制一份追加到末尾,形成一个长度为 的线性数组: 对于任意一个长度为 的连续子区间 (其中 ),它都恰好对应了在原环形结构中从第 堆开始顺时针遍历整整一圈的某种线性展开! 因此,我们只需在长度为 的数组上执行一次标准的区间 DP,最后在所有长度为 的合法区间 中取极值: 这样只需耗费常数略大的 时间即可一次性搞定所有环形断点。

3. 区间动态规划(Interval DP)的状态设计与转移方程

区间 DP 的核心特征是:以“区间长度”作为动态规划的递推阶段,从小区间的最优解逐步推导出大区间的最优解。

  • 前缀和数组优化: 任意连续子区间 内的所有石子总数可以通过前缀和在 时间内求得: 无论这两堆石子内部是按什么顺序合并的,当它们最终合并为 这一整堆时,最后一步产生的合并得分必然等于该区间内所有石子的数量之和 。

  • 状态定义:

    • :将下标从 到 的石子堆合并成一堆所能获得的最小得分;
    • :将下标从 到 的石子堆合并成一堆所能获得的最大得分。
  • 边界与基础条件: 当区间长度为 (即 )时,本身就是一堆石子,无需发生任何合并操作,得分恒为 : 其余非对角线状态, 赋极大值(如 ), 赋 或 。

  • 状态转移方程: 对于区间 (长度 ),最后一次合并必然发生在某个分割点 ()处,将左半段 与右半段 两大堆合并为最终一堆:

4. 循环阶段次序:为什么必须按照“区间长度”外层循环?

在区间 DP 中,循环层级的顺序是决定算法正确性的生命线。

  • 常见错误:外层枚举起点 ,内层枚举终点 。当计算 时,需要用到子问题 。但若采用 正向循环,当处理当前行 时,行号更大的 ()在后续外层迭代中可能根本没有计算完,直接违反了动态规划的无后效性与拓扑有序性。
  • 标准写法:
    1. 最外层循环:枚举区间长度 ,从 递增到 ;
    2. 第二层循环:枚举区间左端点 ,计算右端点 (需满足 );
    3. 最内层循环:枚举分割点 ,从 遍历至 。 由于任何子区间 和 的长度都严格小于 ,它们在之前的 阶段中已经全部求解完毕,能够安全无误地参与状态转移。

5. 复杂度剖析与运行指标

  • 时间复杂度:
    • 数组倍长后规模为 ;
    • 外层长度循环 ,共 次;
    • 中层起点循环 约 次;
    • 内层分割点 循环 次;
    • 总运算次数为: 对于 , 次循环操作,在现代评测机上仅需 ,远远低于 的时限要求。
  • 空间复杂度:
    • 状态矩阵大小为 ;
    • 存储 、 两个整型二维数组仅需 ,对内存的消耗微乎其微。

6. 核心考点与竞赛避坑指南

  1. 破环成链的外层长度上限: 虽然数组长度扩展至 ,但由于我们最终只需要合并 堆石子,外层循环的区间长度 只需枚举到 即可,无需枚举到 。这直接节约了一半的常数时间开销。
  2. 单堆特判( 的边界): 当 时,无需进行任何合并操作,最小得分与最大得分均为 。代码中外层循环 从 2 开始,对于 循环直接不执行,最终答案统计取得 ,天然契合单点边界。
  3. 极值初始化的正确范围: 最小得分 的初始值不可过大导致加法溢出(如使用 INT_MAX 与前缀和相加可能发生整型上溢),设定为 1e9 既足够大又绝对安全。

完整参考代码(C++11 规范)

C++87 行
/**
 * 题目: 【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;
}
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

CSP / NOIP 信奥竞赛 · CSP-S⏱️ 15 分钟

【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1113 [USACO02FEB] 杂务

生活与工业生产中的工序流水线调度,天然蕴含着严苛的时序依赖:地基未筑不可起高楼,原料未至不可开炉灶。洛谷 P1113「[USACO02FEB] 杂务」以牧场日常作业为背景,生动抽象出工程管理与图论中的核心模型——有向无环图(DAG)的关键路径与最早完成时间计算(Crit...

阅读全文 →
CSP / NOIP 信奥竞赛 · CSP-S⏱️ 20 分钟

【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3371 【模板】单源最短路径(弱化版)

在交通网络寻径、物流供应链调度与通信路由协议中,求解从指定始发枢纽到网络中所有连通节点的最优开销,是离散优化与图论的核心基石。洛谷 P3371「【模板】单源最短路径(弱化版)」给出了非负权有向图单源最短路径(Single-Source Shortest Path, SS...

阅读全文 →
CSP / NOIP 信奥竞赛 · CSP-S⏱️ 18 分钟

【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3366 【模板】最小生成树

在通信基站管网布线、电力网架设以及交通枢纽规划等重大工程中,如何在保证所有节点相互连通的前提下,使铺设线路的总建设开销(边权之和)达到全局最小,是经典的最小生成树(Minimum Spanning Tree, MST)离散优化问题。洛谷 P3366「【模板】最小生成树」...

阅读全文 →
OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!