题解 | #卡牌游戏#

题目链接

题目描述

有 $n$ 张卡牌排成一行，每张卡牌有分值 $a_i$ 。每次操作可以选择最左端的连续若干张（至少一张）卡牌，将它们替换为一张新卡牌，新卡牌的分值为被替换卡牌的分值之和。每次操作后，新卡牌的分值会累加到总分中。求能够获得的最高总分。

解题思路

这是一个典型的动态规划问题。经过用户的指正，先前版本对题目规则的理解有误。核心规则是**“每次操作，旺仔哥哥可以选取位于序列最左端的连续若干张卡牌（不少于2张）”**。

基于这个关键点，我们重新设计DP方案：令 $dp[i]$ 为对前 $i$ 张卡牌（即 a[0] 到 a[i-1]）进行一系列操作，最终合并为一张牌时，所能获得的最大总分。同时，令 $s[i]$ 为原序列的前缀和，即 $s[i] = \sum_{k=0}^{i} a[k]$ 。

为了计算 $dp[i]$ （其中 $i \ge 2$ ），我们考虑形成这张最终牌的最后一次操作。这次操作必然是合并了 $k$ 张卡牌（ $k \ge 2$ ）。这些卡牌的最左边一张，在操作前是代表前 $j$ 张原始卡牌的合成卡（ $0 \le j < i$ ），其余的是原始卡牌。

无论中间过程如何，这次操作获得的得分为当前合并的所有卡牌的原始分值之和，也就是前缀和 $s[i-1]$ 。
在这次操作之前，我们在前 $j$ 张牌上获得的最大分数是 $dp[j]$ 。我们定义 $dp[0] = 0$ ，代表游戏未开始，分数为0。
关键约束：由于每次合并至少需要2张牌，我们不可能只合并 a[0] 这一张牌就结束。因此， $dp[1]$ 是一个无法达成的无效状态。这意味着，当我们计算 $dp[i]$ 时，它不可能从 $dp[1]$ 这个状态转移而来。

所以，状态转移方程为： $dp[i] = s[i-1] + \max_{j \in \{0, 2, 3, ..., i-1\}} (dp[j])$

为了优化计算，我们可以维护一个变量 max_dp_for_prefix 来实时记录 $\max(dp[0], dp[2], dp[3], ...)$ 的值。

当我们计算 $dp[i]$ 时，max_dp_for_prefix 正是 $\max(dp[0], dp[2], ..., dp[i-1])$ 的值。
计算出 $dp[i]$ 后，我们再用它来更新 max_dp_for_prefix，以供后续的 $dp$ 计算使用。

最后，因为题目说明“可以随时宣布游戏结束”，最优解可能是在合并前 $i$ 张牌后就停止。因此，最终的答案是所有有效的 $dp[i]$ （ $i \ge 2$ ）中的最大值。如果所有可能获得的分数都为负，那么最优策略是不进行任何操作，获得0分。

代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

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

    int n;
    cin >> n;

    if (n < 2) {
        cout << 0 << "\n";
        return 0;
    }

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

    // s[i] 存储 a[0]...a[i] 的和
    vector<long long> s(n);
    s[0] = a[0];
    for (int i = 1; i < n; ++i) {
        s[i] = s[i - 1] + a[i];
    }

    // dp[i] 表示对前 i 张牌 (a[0]..a[i-1]) 操作，最终合成一张牌的最大得分
    vector<long long> dp(n + 1, 0);
    
    // 记录 dp[0], dp[2], dp[3]... 中的最大值
    long long max_dp_for_prefix = 0; 
    long long overall_max_score = 0;

    // i 是牌的数量，从 2 到 n
    for (int i = 2; i <= n; ++i) {
        // 状态转移方程
        dp[i] = s[i - 1] + max_dp_for_prefix;
        // 更新 dp 前缀最大值，用于下一次转移
        max_dp_for_prefix = max(max_dp_for_prefix, dp[i]);
        // 更新全局最大分数
        overall_max_score = max(overall_max_score, dp[i]);
    }

    cout << overall_max_score << "\n";

    return 0;
}

算法及复杂度

算法：动态规划
时间复杂度：计算前缀和数组需要 $O(n)$ 的时间，DP过程遍历一次数组，也需要 $O(n)$ 的时间。因此，总时间复杂度为 $O(n)$ 。
空间复杂度：需要数组来存储前缀和和DP状态，因此空间复杂度为 $O(n)$ 。