P1880 [NOI1995] 石子合并 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1880，日期见页头。两边不一致时信原站。

题目描述

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

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

输入格式

数据的第 1 行是正整数 N，表示有 N 堆石子。

第 2 行有 N 个整数，第 i 个整数 aᵢ 表示第 i 堆石子的个数。

输出格式

输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。

说明/提示

1 ≤ N ≤ 100，0 ≤ aᵢ ≤ 20。

输入输出样例

输入

4
4 5 9 4

输出

43
54

四堆摆成一个圈：4 5 9 4（第 4 堆和第 1 堆也相邻）。

⚠ 这一组样例最值得注意的是它只挡住了一半：「没破环」那一版打出 44 / 54 —— 最小那一问被抓，最大那一问一模一样。而贪心那一版 43 / 54，两问全放过。

1第一版：把它当成上一题（没破环）

P1775 刚做完，最自然的动作是把那份代码原样交上去 —— 它丢掉的正是这道题唯一的新东西：第 N 堆和第 1 堆也是相邻的。

p1880Line.cpp✗ 第一版：没破环，当直线做

// ✗ P1880 的第一版：**根本没破环** —— 直接照 [P1775](/sol/p1775/) 那道直线题做。
//
// 这是最自然的第一反应：「不就是石子合并吗」，于是把上一题的代码原样交上去。
// 它丢掉的正是这道题唯一的新东西：**第 N 堆和第 1 堆也是相邻的**。
//
// ★ 它的方向是可以先说死的：环上允许的合并方式**比链上多**（多了「跨过头尾」那一类）
//   ⇒ 它的最小值**恒 ≥ 正解的最小值**，最大值**恒 ≤ 正解的最大值**。
//   页面上那张表把这两条各钉了 300 / 300。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; i++) { long long x; if (scanf("%lld", &x) != 1) return 0; s[i] = s[i - 1] + x; }

    vector<vector<long long>> lo(n + 2, vector<long long>(n + 2, 0));
    vector<vector<long long>> hi(n + 2, vector<long long>(n + 2, 0));
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            long long best = LLONG_MAX, most = LLONG_MIN;
            for (int k = l; k < r; k++) {
                best = min(best, lo[l][k] + lo[k + 1][r]);
                most = max(most, hi[l][k] + hi[k + 1][r]);
            }
            long long sum = s[r] - s[l - 1];
            lo[l][r] = best + sum;
            hi[l][r] = most + sum;
        }
    printf("%lld\n%lld\n", lo[1][n], hi[1][n]);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 它错的方向不用跑就知道 —— 而且两问方向相反

环上允许的合并方式比链上多（多了「跨过头尾」那一整类）⇒ 可行集更大 ⇒


它的最小值 ≥ 正解的最小值	★ 300 / 300
它的最大值 ≤ 正解的最大值	★ 300 / 300

⇒ 这就是上一页那条规矩的原样复用： 「答案偏大还是偏小」由「你解的是放宽了的问题还是收紧了的问题」决定。 这一次它一次给出两个方向 —— 因为同一份代码要回答两个问题。

⚠ 而两问的抓获率差 1.8 倍（各 300 轮）

	最小那一问	最大那一问
「没破环」被抓	85 / 300	★ 153 / 300

★ 官方样例正好落在只有最小那一问被抓的那一边（44 vs 43，而最大两边都是 54）。 ⇒ 「样例挡不挡得住」在多问的题上要分问说 （第 22 章 P1020 那页是「按问给分」，这里是「按问被抓」）。

2★★ 关键的一步：破环成链

★ 把 N 个数复制一遍接在后面

    原环：a₁ a₂ … a_N              （a_N 和 a₁ 相邻）
    链  ：a₁ a₂ … a_N a₁ a₂ … a_N   （2N 个位置）

    环上「合并成一堆」的任何一种方案
      ⟺ 链上某个**长度恰好为 N** 的区间 [i, i+N−1]
    ⇒ 答案 = min（或 max）over i ∈ [1, N] of f[i][i+N−1]

于是环形问题被原样翻译成了第 26 章正文那道题 —— 区间 DP 一个字都不用改，改的只有「链有多长」和「最后读哪些格子」。

p1880.cpp★ 这一版就能 AC（两问一起算）

// P1880 [NOI1995] 石子合并 —— ★ 这一版就能 AC。
//
// 和[本章正文那道题](/ch/26-interval-dp/)（也就是 [P1775](/sol/p1775/)）只差两处：
//   ① 石子摆成**一个圆**（第 N 堆和第 1 堆也相邻）；
//   ② 要**同时**求最小得分和最大得分。
//
// ★★ 关键的一步：**破环成链** —— 把这 N 个数**复制一遍接在后面**，得到 2N 个数，
//   然后在这条链上跑普通的区间 DP。环上的任何一种「合并成一堆」的方案，
//   在链上都对应某个**长度恰好为 N** 的区间 [i, i+N-1]；反过来也一样。
//   ⇒ 答案 = min（或 max）over i ∈ [1, N] of f[i][i+N-1]。
//
// ⚠ 两处最容易漏：
//   ① 数组要开 **2N**（链有 2N 个位置，区间长度最长到 N）；
//   ② 答案**不是 f[1][N]** —— 那只是「从第 1 堆断开」的那一种（见 p1880First.cpp，
//      它和「根本没破环」逐组相等）。
//
// ★ 最大值那一半只要把 min 换成 max，一个字都不用多写（但初值要跟着换）。
// 规模：2N = 200 ⇒ 转移约 130 万次，两遍也就是几百万次。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    int m = 2 * n;
    vector<long long> s(m + 1, 0);
    vector<long long> a(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (scanf("%lld", &a[i]) != 1) return 0;
        a[i + n] = a[i];                              // ★ 破环成链：复制一遍
    }
    for (int i = 1; i <= m; i++) s[i] = s[i - 1] + a[i];

    vector<vector<long long>> lo(m + 2, vector<long long>(m + 2, 0));
    vector<vector<long long>> hi(m + 2, vector<long long>(m + 2, 0));
    for (int len = 2; len <= n; len++)                // 区间长度最长到 n（不是 2n）
        for (int l = 1; l + len - 1 <= m; l++) {
            int r = l + len - 1;
            long long best = LLONG_MAX, most = LLONG_MIN;
            for (int k = l; k < r; k++) {
                best = min(best, lo[l][k] + lo[k + 1][r]);
                most = max(most, hi[l][k] + hi[k + 1][r]);
            }
            long long sum = s[r] - s[l - 1];
            lo[l][r] = best + sum;
            hi[l][r] = most + sum;
        }

    long long ansLo = LLONG_MAX, ansHi = LLONG_MIN;
    for (int i = 1; i <= n; i++) {                    // ★ 每个起点都要看一遍
        ansLo = min(ansLo, lo[i][i + n - 1]);
        ansHi = max(ansHi, hi[i][i + n - 1]);
    }
    printf("%lld\n%lld\n", ansLo, ansHi);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 规模：一道三十秒的算术题


链长 `2N = 200`，区间长度最长到 `N = 100` ⇒ 转移	661 650 次（两问共用同一层循环）
顶格 `N = 100`、每堆 20 的答案	13 440 ／ 100 980
不用跑的上界 `N × max(aᵢ) × (N−1)`	198 000 ⇒ `int` 绰绰有余

3★ 「破了环却只取 f[1][n]」—— 它算了什么，能说死

破环成链最常见的半途而废：数组开对了、链也铺好了，最后那一步忘了「每个起点都要看一遍」。

p1880First.cpp✗ 只取 f[1][n]

// ✗ P1880 的第二版：破了环、复制了一遍，**答案却只取 f[1][n]**。
//
// 这是「破环成链」最常见的半途而废：数组开对了、链也铺好了，
// 最后那一步忘了「**每个起点都要看一遍**」。
//
// ★ 而它算了什么，是可以说死的：只取 f[1][n] 就等于「规定必须从第 1 堆和第 N 堆之间断开」
//   —— 那恰恰就是**没破环**的那道直线题。
//   ⇒ 页面上钉了这条恒等式：它和 p1880Line.cpp **逐组相等，300 / 300**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    int m = 2 * n;
    vector<long long> a(m + 1, 0), s(m + 1, 0);
    for (int i = 1; i <= n; i++) { if (scanf("%lld", &a[i]) != 1) return 0; a[i + n] = a[i]; }
    for (int i = 1; i <= m; i++) s[i] = s[i - 1] + a[i];

    vector<vector<long long>> lo(m + 2, vector<long long>(m + 2, 0));
    vector<vector<long long>> hi(m + 2, vector<long long>(m + 2, 0));
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= m; l++) {
            int r = l + len - 1;
            long long best = LLONG_MAX, most = LLONG_MIN;
            for (int k = l; k < r; k++) {
                best = min(best, lo[l][k] + lo[k + 1][r]);
                most = max(most, hi[l][k] + hi[k + 1][r]);
            }
            long long sum = s[r] - s[l - 1];
            lo[l][r] = best + sum;
            hi[l][r] = most + sum;
        }
    printf("%lld\n%lld\n", lo[1][n], hi[1][n]);      // ✗ 只看了「从第 1 堆断开」这一种
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 它恒等于「根本没破环」的那一版


300 轮：它 vs 「没破环」那一版（两问都比）	★ 300 / 300 逐组相等
它被抓	203 / 300

⇒ 只取 f[1][n] 就等于规定必须从第 1 堆和第 N 堆之间断开 —— 那恰恰就是直线版。 ★ 又一次「说清楚一个 bug 算了什么，比说它错了有用得多」：说清之后，「它和直线版一样会被样例的最小那一问抓住、最大那一问放过」是白送的推论。

4★ 题单那句「那个错误贪心对最大值同样是错的」——量出来

p1880Greedy.cpp✗ 贪心：最小问挑最小的一对，最大问挑最大的一对

// ✗ P1880 的贪心版：最小那一问「每次合相邻两堆里和**最小**的一对」，
//   最大那一问「每次合相邻两堆里和**最大**的一对」（都在环上）。
//
// 题单里那句话说的就是它：「求最大值只需要把 min 换成 max ——
// **但那个错误贪心对最大值同样是错的**」。这一版就是拿来把那句话量出来的。
//
// ★ 方向照旧能先说死：它给出的是**一个合法方案** ⇒
//   最小那一问恒 ≥ 正解，最大那一问恒 ≤ 正解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/** want = 0 取最小的一对，want = 1 取最大的一对 */
static ll run(vector<ll> a, int want) {
    ll sum = 0;
    while (a.size() > 1) {
        int n = (int)a.size(), best = 0;
        ll bv = a[0] + a[1 % n];
        for (int i = 1; i < n; i++) {
            ll v = a[i] + a[(i + 1) % n];
            if ((want == 0 && v < bv) || (want == 1 && v > bv)) { bv = v; best = i; }
        }
        int j = (best + 1) % n;
        vector<ll> b;
        if (j == 0) {
            b.push_back(bv);
            for (int t = 1; t < n - 1; t++) b.push_back(a[t]);
        } else {
            for (int t = 0; t < n; t++) {
                if (t == best) { b.push_back(bv); t++; }
                else b.push_back(a[t]);
            }
        }
        sum += bv;
        a = b;
    }
    return sum;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) if (scanf("%lld", &a[i]) != 1) return 0;
    printf("%lld\n%lld\n", run(a, 0), run(a, 1));
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

	最小那一问	最大那一问
方向（不用跑就知道）	恒 ≥ 正解（300/300）	恒 ≤ 正解（300/300）
默认档被抓	16 / 300	43 / 300

⇒ 题单那句话是对的：两问都错。

★★ 而「只被抓 16 轮」这个数，主语是值域 —— 拧一下它，两问方向相反

只改每堆石子数的上限（各 300 轮，n ≤ 8）：

值域	0~2	0~5	0~20（题面顶格）	0~100（★ 已越出题面）
贪心·最小那一问被抓	★ 0	4	16	★ 26
贪心·最大那一问被抓	★ 44	47	43	★ 34
而「存在两对相邻和相等」的轮数	280	244	155	72

★★★ 同一把旋钮，把两问推向相反方向 —— 最小那一问越拧越容易抓，最大那一问反而越来越难抓。（本书第五次量到「一个旋钮两个方向」，而这一次 两个方向属于同一道题的两问。） ★ 第三行给出了一半解释：值域越小，并列越多，贪心「怎么选都一样」的机会就越多。

⚠ 而这一页的 16 不能拿去和正文那道题的 114 比 —— 那是另一道题（链，不是环）、另一个档位（6~~9 堆、值 1~~100）。 抓获率永远是一个连着「哪道题、哪一档」的数。

5度量程序、生成器和参照物

p1880Count.cpp度量程序（本页所有数字都出自它）

p1880Gen.cpp数据生成器

p1880Brute.cpp参照物：在环上枚举合并顺序（300 轮不一致 0 轮）

6一页纸


★★ 关键的一步	破环成链：复制一遍接在后面，跑长度恰好为 `N` 的区间；答案取每个起点的最好值
规模	链长 200、转移 661 650 次；上界 198 000 ⇒ `int` 够
第一版：没破环	最小恒 ≥、最大恒 ≤（各 300/300）—— ★ 方向不用跑就知道
⚠ 而两问的抓获率差 1.8 倍	最小 85 / 最大 153；★ 官方样例只挡住最小那一问
「只取 `f[1][n]`」	★ ≡ 根本没破环（300/300 逐组相等），被抓 203
题单那句话	贪心两问都错（最小 16 / 最大 43）
★★ 而那个 16 的主语是值域	值域 2 → 100：最小那一问 0 → 26，最大那一问 44 → 34 —— ★ 同一把旋钮，两问方向相反

洛谷 P1880 [NOI1995] 石子合并

0题目原文（本地存了一份）

输入

输出

1第一版：把它当成上一题（没破环）

2★★ 关键的一步：破环成链

3★ 「破了环却只取 f[1][n]」—— 它算了什么，能说死

4★ 题单那句「那个错误贪心对最大值同样是错的」——量出来

5度量程序、生成器和参照物

6一页纸