P1880 石子合并

P1880 石子合并

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

luogu-P1880 [NOI1995] 石子合并

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

题目描述

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

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

输入格式

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

第 22 行有 NN 个整数,第 ii 个整数 aia_i 表示第 ii 堆石子的个数。

输出格式

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

样例 #1

样例输入 #1

4
4 5 9 4

样例输出 #1

43
54

提示

1≤N≤1001\leq N\leq 100,0≤ai≤200\leq a_i\leq 20。


题目深度剖析

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

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

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

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

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

  • 朴素做法的缺陷:若枚举切开环的位置(共有 NN 种不同的断开方式),每次重新跑一遍 O(N3)O(N^3) 的线性区间 DP,总时间复杂度将上升至 O(N⋅N3)=O(N4)O(N \cdot N^3) = O(N^4)。对于 N=100N = 100,1004=108100^4 = 10^8 次运算,在 1 秒时限内较为勉强。
  • 破环成链(断环为链)经典技巧: 将长度为 NN 的原序列直接复制一份追加到末尾,形成一个长度为 2N2N 的线性数组: a=[a1,a2,…,aN,a1,a2,…,aN]a = [a_1, a_2, \dots, a_N, a_1, a_2, \dots, a_N] 对于任意一个长度为 NN 的连续子区间 [i,i+N−1][i, i + N - 1](其中 1≤i≤N1 \le i \le N),它都恰好对应了在原环形结构中从第 ii 堆开始顺时针遍历整整一圈的某种线性展开! 因此,我们只需在长度为 2N2N 的数组上执行一次标准的区间 DP,最后在所有长度为 NN 的合法区间 [i,i+N−1][i, i + N - 1] 中取极值: ans_min=min⁡1≤i≤Ndp_min[i][i+N−1]\text{ans\_min} = \min_{1 \le i \le N} dp\_min[i][i + N - 1] ans_max=max⁡1≤i≤Ndp_max[i][i+N−1]\text{ans\_max} = \max_{1 \le i \le N} dp\_max[i][i + N - 1] 这样只需耗费常数略大的 O((2N)3)O((2N)^3) 时间即可一次性搞定所有环形断点。

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

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

  • 前缀和数组优化: 任意连续子区间 [i,j][i, j] 内的所有石子总数可以通过前缀和在 O(1)O(1) 时间内求得:

    sum[k]=∑t=1ka[t]  ⟹  ∑t=ija[t]=sum[j]−sum[i−1]sum[k] = \sum_{t=1}^k a[t] \implies \sum_{t=i}^j a[t] = sum[j] - sum[i - 1]

    无论这两堆石子内部是按什么顺序合并的,当它们最终合并为 [i,j][i, j] 这一整堆时,最后一步产生的合并得分必然等于该区间内所有石子的数量之和 ∑t=ijat\sum_{t=i}^j a_t。

  • 状态定义:

    • dp_min[i][j]dp\_min[i][j]:将下标从 ii 到 jj 的石子堆合并成一堆所能获得的最小得分;
    • dp_max[i][j]dp\_max[i][j]:将下标从 ii 到 jj 的石子堆合并成一堆所能获得的最大得分。
  • 边界与基础条件: 当区间长度为 11(即 i=ji = j)时,本身就是一堆石子,无需发生任何合并操作,得分恒为 00:

    dp_min[i][i]=0,dp_max[i][i]=0dp\_min[i][i] = 0, \quad dp\_max[i][i] = 0

    其余非对角线状态,dp_mindp\_min 赋极大值(如 10910^9),dp_maxdp\_max 赋 −1-1 或 00。

  • 状态转移方程: 对于区间 [i,j][i, j](长度 len=j−i+1≥2len = j - i + 1 \ge 2),最后一次合并必然发生在某个分割点 kk(i≤k<ji \le k < j)处,将左半段 [i,k][i, k] 与右半段 [k+1,j][k + 1, j] 两大堆合并为最终一堆:

    dp_min[i][j]=min⁡i≤k<j(dp_min[i][k]+dp_min[k+1][j])+(sum[j]−sum[i−1])dp\_min[i][j] = \min_{i \le k < j} \left( dp\_min[i][k] + dp\_min[k + 1][j] \right) + (sum[j] - sum[i - 1])

    dp_max[i][j]=max⁡i≤k<j(dp_max[i][k]+dp_max[k+1][j])+(sum[j]−sum[i−1])dp\_max[i][j] = \max_{i \le k < j} \left( dp\_max[i][k] + dp\_max[k + 1][j] \right) + (sum[j] - sum[i - 1])

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

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

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

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

  • 时间复杂度:
    • 数组倍长后规模为 2N2N;
    • 外层长度循环 len∈[2,N]len \in [2, N],共 N−1N - 1 次;
    • 中层起点循环 ii 约 2N2N 次;
    • 内层分割点 kk 循环 len−1len - 1 次;
    • 总运算次数为: ∑len=2N(2N−len+1)(len−1)≈16×(2N)×N2=13N3\sum_{len=2}^N (2N - len + 1)(len - 1) \approx \frac{1}{6} \times (2N) \times N^2 = \frac{1}{3} N^3 对于 N=100N = 100,N3/3≈3.3×105N^3 / 3 \approx 3.3 \times 10^5 次循环操作,在现代评测机上仅需 2∼5 ms2 \sim 5 \text{ ms},远远低于 1.0 s1.0 \text{ s} 的时限要求。
  • 空间复杂度:
    • 状态矩阵大小为 2N×2N=200×2002N \times 2N = 200 \times 200;
    • 存储 dp_mindp\_min、dp_maxdp\_max 两个整型二维数组仅需 205×205×4×2≈336 KB205 \times 205 \times 4 \times 2 \approx 336 \text{ KB},对内存的消耗微乎其微。

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

  1. 破环成链的外层长度上限: 虽然数组长度扩展至 2N2N,但由于我们最终只需要合并 NN 堆石子,外层循环的区间长度 lenlen 只需枚举到 NN 即可,无需枚举到 2N2N。这直接节约了一半的常数时间开销。
  2. 单堆特判(N=1N = 1 的边界): 当 N=1N = 1 时,无需进行任何合并操作,最小得分与最大得分均为 00。代码中外层循环 lenlen 从 2 开始,对于 N=1N = 1 循环直接不执行,最终答案统计取得 dp[1][1]=0dp[1][1] = 0,天然契合单点边界。
  3. 极值初始化的正确范围: 最小得分 dp_mindp\_min 的初始值不可过大导致加法溢出(如使用 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;
}

本文由coderli.com原创,按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群: 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于