[省选联考 2020 B 卷] 卡牌游戏

GitHub跳转原题关系图返回列表

把每次操作看成选择一个更长的原数组前缀，答案就是所有正的前缀和（下标至少为 2）之和。

OJ: luogu

题目 ID: P6625

难度:普及/提高-

标签:前缀和贪心思维

日期: 2026-06-18 18:08

目录

  1. 题意
  2. 思路
    1. 样例 2 的前缀和
  3. 代码
  4. 复杂度
  5. 总结

题意

有一列卡牌，每次只能选择当前序列最左边连续若干张卡牌，至少 2 张，把它们合并成一张新卡牌。
新卡牌的分值等于这几张卡牌分值之和，并且这次操作会给总分增加同样的值。

你可以做若干次操作，也可以提前停下。问最后总分最大是多少。

思路

先看一个完全按题意搜索所有操作方案的朴素解：

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

using ll = long long;

ll ans = 0;

void dfs(const vector<ll> &cards, ll score) {
    ans = max(ans, score);

    int n = static_cast<int>(cards.size());
    for (int len = 2; len <= n; ++len) {
        ll sum = 0;
        for (int i = 0; i < len; ++i) {
            sum += cards[i];
        }

        vector<ll> next_cards;
        next_cards.push_back(sum);
        for (int i = len; i < n; ++i) {
            next_cards.push_back(cards[i]);
        }

        dfs(next_cards, score + sum);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<ll> cards(n);
    for (int i = 0; i < n; ++i) {
        cin >> cards[i];
    }

    dfs(cards, 0);
    cout << ans << '\n';
    return 0;
}

brute.cpp 每次枚举要合并前几张卡牌，把新序列递归下去。
它很直观，但状态数是指数级的，只能拿来做小数据校验。

这题真正的关键是把“操作过程”换一个角度来看。

设原数组前缀和为 s[i] = a[1] + ... + a[i]。
如果第一次操作选择原数组前 i 张卡牌，那么这次增加的分数就是 s[i]。

更重要的是，后面的操作虽然是在新序列上做，但新序列最左边那张卡牌，始终表示“原数组的某个前缀之和”。
所以每做一次操作，本质上都是把这个前缀继续向右扩展，变成一个更长的前缀。

于是，一组合法操作恰好对应于一串严格递增的前缀下标：

i_1 < i_2 < ... < i_t，且每个 ik>=2i_k >= 2

总得分就是：

s[i_1] + s[i_2] + ... + s[i_t]

也就是说，这题其实是在问：

  • 哪些前缀和可以被选？
  • 选了一个前缀和之后，会不会妨碍以后再选别的？

答案是：

  1. 任意 i>=2i >= 2 的前缀都可以单独作为一次操作的结果；
  2. 只要下标递增，就总能按这个顺序做到；
  3. 所以前缀之间互不冲突。

既然互不冲突，那么最优策略就很直接了：
把所有 大于 0 的前缀和都选上，非正的前缀和直接跳过。

样例 2 的前缀和

这张表展示样例 -4 3 0 7 -3 -5 -3 的前缀和，以及哪些前缀值得选。

i 前缀和 s[i] 是否选入答案
1 -4 不能选，单次操作至少要合并 2 张
2 -1 不选
3 -1 不选
4 6 选
5 3 选
6 -2 不选
7 -5 不选

所以答案就是 6+3=96 + 3 = 9。
这也对应题目给出的最优策略：先做到前缀 4，再做到前缀 5。

实现上只是一次前缀和扫描，这个建模方式和 rbook 的 前缀和 文章是一致的。

代码

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

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    ll prefix_sum = 0;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ll x;
        cin >> x;
        prefix_sum += x;

        // 每一次操作都对应选择一个更长的前缀，产生一次新的前缀和收益。
        if (i >= 2 && prefix_sum > 0) {
            ans += prefix_sum;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

设卡牌数量为 n。

  • 只需从左到右扫描一遍数组。
  • 时间复杂度 O(n)O(n)。
  • 额外空间复杂度 O(1)O(1)。

总结

这题的难点不在实现，而在于看出：

  1. 每次操作得到的分数，其实就是某个原数组前缀和；
  2. 一系列操作，对应的是一串递增的前缀下标；
  3. 这些前缀之间没有冲突，所以把所有正前缀和都加起来就是答案。