纸牌游戏 题解

题目分析

本题是一个在已知对手出牌序列的情况下，规划自己的出牌策略以最大化得分的博弈问题。题目有以下几个关键要素：

1. 胜负判定与得分：每轮双方各出一张牌（0、1、2），胜负关系为 1 胜 0、2 胜 1、0 胜 2。胜者得 $2 \times a_i$ 分，败者得 0 分，平局各得 $a_i$ 分。
2. 对手策略已知：小杨的整个出牌序列 $c_1 \dots c_N$ 在游戏开始前就告诉我们了。
3. 自身换牌限制：我们从第 2 轮开始，要么继续出上一轮的牌，要么换牌。每换一次牌都会产生罚分，第 $t$ 次换牌的罚分为 $b_t$，总罚分是已发生换牌的罚分之和。
4. 目标：最大化总分（每轮得分之和减去换牌总罚分）。

解题思路

由于对手的出牌完全已知，我们可以将每轮针对自己不同出牌能获得的基础得分提前计算出来。剩下的问题就是在「换牌次数」和「罚分」的约束下，选择每轮的出牌，使得总分最大。

这是一个典型的多阶段决策问题，很自然想到用动态规划 (DP) 来解决。我们需要在状态中记录当前轮结束后自己的出牌是什么，以及当前已经换过多少次牌（因为罚分力度与这是第几次换牌有关）。

状态定义

设 $dp[k][j]$ 表示：已经完成了前若干轮，当前自己的出牌为 $k\ (k\in\{0,1,2\})$，且累计已经换了 $j$ 次牌时，能够获得的最大分数。

由于我们只需要上一轮的信息来更新当前轮，因此可以滚动使用数组，不需要保留每一轮的状态。

状态转移

假设我们已经处理完前 $i-1$ 轮，现在要处理第 $i$ 轮（$i \ge 2$）。设 $score(i, k)$ 为在第 $i$ 轮出牌 $k$ 时能从这一轮获得的基础得分（$= result(k, c_i) \times a_i$）。

从上一轮到这一轮，有两种选择：

1. 不换牌：仍然使用上一轮的出牌 $k$，换牌次数 $j$ 不变。
   此时：$dp[k][j] \leftarrow dp[k][j] + score(i, k)$。

2. 换牌：从上一轮的出牌 $l$ 换成这一轮的 $k$（$l \neq k$），换牌次数 $j$ 增加 1，并扣除第 $j$ 次换牌的罚分 $b_j$。
   此时：$dp[k][j] \leftarrow \max\big(dp[k][j],\ dp[l][j-1] + score(i, k) - b_j\big)$。

初始状态为第 1 轮结束后：
$dp[k][0] = score(1, k)$，对所有 $k\in\{0,1,2\}$。

最终答案即为所有轮结束后，所有 $k$ 和所有换牌次数 $j$ 下的 $dp[k][j]$ 的最大值。

算法说明

上述 DP 在实现时有几个要点：

• 由于换牌次数 $j$ 在转移时只用到 $j-1$ 的状态，为了避免用本轮更新的值去更新本轮的其他状态，我们对 $j$ 采用倒序枚举（从 $i-1$ 向下到 0）。这类似于 0/1 背包的滚动数组优化。
• 转移时先加上当前轮的得分（不换牌情况），再尝试用 $j-1$ 的状态换牌。
• 胜负判定函数 $result(x, y)$ 返回：$2$ 表示 $x$ 胜 $y$，$1$ 表示平局，$0$ 表示 $x$ 负于 $y$。

胜负判定表

代码中 result(x, y) 利用数学关系简洁实现：

• 若 x == y + 1 || x == y - 2 则 $x$ 胜 $y$（返回 2）；
• 若 x == y 则平局（返回 1）；
• 其余为负（返回 0）。

时间复杂度分析

• 状态数：$O(N)$ 个换牌次数，常数 $3$ 种出牌，总状态数为 $O(N)$。
• 每轮转移时枚举 $j$ 和当前出牌 $k$、上一轮出牌 $l$，每轮操作量为 $O(3 \times 3 \times i) = O(i)$。
• 总时间复杂度：$\sum_{i=2}^{N} O(i) = O(N^2)$。
• 空间复杂度：用滚动数组优化为 $O(N)$。

$N \le 1000$，$N^2 = 10^6$，完全可以在 1 秒内完成。

参考代码

cpp
复制
1#include <iostream>
2#include <cstring>
3#include <algorithm>
4using namespace std;
5
6const int max_n = 1005;
7const int INF = -2e9; // 用于初始化极小值
8
9int n;
10int a[max_n], b[max_n], c[max_n];
11int dp[3][max_n]; // dp[k][j]: 当前出牌为k，已经换牌j次的最大分数
12
13// 判断x对y的胜负，返回倍数：2胜、1平、0负
14int result(int x, int y) {
15    if (x == y + 1 || x == y - 2) return 2;
16    if (x == y) return 1;
17    return 0;
18}
19
20int main() {
21    ios::sync_with_stdio(false);
22    cin.tie(0);
23    
24    cin >> n;
25    for (int i = 1; i <= n; ++i) cin >> a[i];
26    for (int i = 1; i < n; ++i)  cin >> b[i];
27    for (int i = 1; i <= n; ++i) cin >> c[i];
28    
29    // 初始化dp为极小值，注意memset(...,128,...)会将每个字节填充为0x80
30    // 对于int相当于一个较大的负数，可以安全地用于max比较
31    memset(dp, 128, sizeof(dp));
32    
33    // 第1轮初始状态：换牌次数为0，出牌为k
34    for (int k = 0; k < 3; ++k) {
35        dp[k][0] = result(k, c[1]) * a[1];
36    }
37    
38    // 从第2轮开始递推
39    for (int i = 2; i <= n; ++i) {
40        // 倒序枚举换牌次数，避免状态覆盖
41        for (int j = i - 1; j >= 0; --j) {
42            for (int k = 0; k < 3; ++k) {
43                int curr_score = result(k, c[i]) * a[i];
44                // 情况1：不换牌，保持出牌k
45                dp[k][j] = dp[k][j] + curr_score;
46                // 情况2：换牌，从上一轮的l换成k，这是第j次换牌
47                if (j > 0) {
48                    for (int l = 0; l < 3; ++l) {
49                        if (l == k) continue; // 同牌不需要换
50                        dp[k][j] = max(dp[k][j], dp[l][j - 1] + curr_score - b[j]);
51                    }
52                }
53            }
54        }
55    }
56    
57    // 在所有轮结束后的所有状态中取最大值
58    int ans = -2e9;
59    for (int j = 0; j < n; ++j) {
60        for (int k = 0; k < 3; ++k) {
61            ans = max(ans, dp[k][j]);
62        }
63    }
64    
65    cout << ans << '\n';
66    return 0;
67}

代码解释

1. result(x, y) 函数：根据规则快速返回得分倍数。
2. 初始化：memset(dp, 128, sizeof(dp)) 将 dp 数组初始化为一个很小的负数（每个字节 0x80），防止未计算的状态影响最大值选取。
3. 第 1 轮处理：直接根据三种出牌计算基础得分，换牌次数为 0。
4. 递推过程：
   • 外层循环 i 遍历第 2 到第 N 轮。
   • 中层循环 j 倒序遍历当前可能的最大换牌次数，保证更新 dp[k][j] 时使用的 dp[l][j-1] 还是上一轮的值。
   • 内层循环 k 枚举当前轮出牌，计算该轮得分，并分别处理「不换牌」和「换牌」的转移。
5. 答案统计：遍历所有 k 和 j，取 dp[k][j] 的最大值输出。

总结

本题的难点在于合理设计状态以处理「换牌次数与罚分顺序相关」的条件。通过将第几次换牌作为 DP 的第二维，并将罚分 $b_j$ 放在转移时扣除，可以很自然地解决问题。倒序枚举换牌次数是滚动数组优化的常见技巧，保证了状态转移的正确性。整道题考察了选手对动态规划状态设计及转移顺序的掌握程度。