GESP 题解库 / 7 级题解 / [GESP202312 七级] 纸牌游戏 · 第 19 / 24 题
GESP202312 七级 · P10111 · 中等

纸牌游戏

小杨 N 轮出牌已知;你每轮"保持不变"或"换牌",换 t 次扣 b₁+…+b_t 分,求最多得分。

🃏
N ≤ 1000
游戏轮数
🔢
0 / 1 / 2
双方的三张牌
⚡
O(3 · N²)
时间复杂度
🎯
dp[轮][出的牌][换牌次数]
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

你和小杨各有三张牌:0、1、2。一共进行 N 轮游戏,每轮双方各出一张牌,按 1 胜 0、2 胜 1、0 胜 2 的规则定胜负。第 i 轮的胜者得 2 · aᵢ 分,败者得 0 分;若两人出牌相同则为平局,双方各得 aᵢ 分。

小杨会在开局前就确定他全部 N 轮的出牌 c₁ … c_N,并把计划告诉你。而你从第 2 轮开始,每轮要么继续出上一轮出的牌,要么换一次牌(换牌次数加一)。游戏结束时如果你一共换了 t 次牌,就要额外扣掉 b₁ + b₂ + … + b_t 分(第 t 次换牌扣 b_t 分,最多换 N − 1 次)。

请你计算:最多能获得多少分?

输入共 4 行:N;a₁ … a_N;b₁ … b_{N−1};c₁ … c_N。

💡
人话翻译:这是一道"收益 + 罚分"交织的 DP。
关键句式是"换牌次数决定罚分":第 1 次换牌扣 b₁,第 2 次扣 b₂,第 3 次扣 b₃……所以"我现在换了 2 次牌"这个信息必须被记住,因为它决定了"下一次换牌要花多少钱"。
于是状态写成 dp[i][x][t]:前 i 轮、第 i 轮出的牌是 x、累计已换牌 t 次时的最大得分。
第 1 轮可以随便出(属于起点,不扣换牌分),之后每轮二选一:保持(不扣分)或换牌(扣 b_{t+1},t 加一),再加上本轮的得分,取最大值。

🔍 关键词提取

动态规划换牌次数进状态滚动数组收益函数

已知条件

项目说明
输入第一行 N;第二行 a₁ … a_N;第三行 b₁ … b_{N−1};第四行 c₁ … c_N
输出一个整数:你最多能获得的分数
数据范围N ≤ 1000,0 ≤ aᵢ, bᵢ ≤ 10⁶
胜负规则1 胜 0,2 胜 1,0 胜 2;出牌相同则平局
得分规则胜者 2 · aᵢ 分,败者 0 分,平局双方各 aᵢ 分
换牌规则第 1 轮自由出牌;此后每轮"保持"或"换牌",换 t 次扣 b₁ + … + b_t

需要解决的问题

02
思维导图
整理解题思路的全貌
🃏 dp[i][x][t]:轮次 × 出的牌 × 换牌次数
🧠 状态设计
dp[i][x][t]:前 i 轮、第 i 轮出 x、已换 t 次的最大得分
t 上限 N − 1(最多每轮都换)
第 1 轮 t = 0,不扣换牌分
答案 = max over x, t of dp[N][x][t]
🔁 转移(第 i+1 轮出 c′)
c′ 与 x 相同:保持,得分 +score(c′, c_{i+1})
c′ 与 x 不同:换牌,得分 −b_{t+1} + score(c′, c_{i+1})
换牌后 t 加一
两种情况都取 max
🧮 收益函数 score(x, y)
平局(x == y):得 aᵢ
取胜(x − y 与 3 同余 1):得 2 · aᵢ
落败:得 0
唯一依赖的输入是 aᵢ 与小杨的 cᵢ
⚠️ 易错点
胜者得分忘记乘 2
罚分写成固定的一个数(应随第几次换牌变化)
第 1 轮就扣了换牌分
b 的下标写成 b_t 而不是 b_{t+1}
03
样例手算推导
两个样例的完整推演

🧮 样例 1:N = 4,答案 219

数据:a = [1, 2, 10, 100],b = [1, 100, 1],c = [1, 1, 2, 0]。

最优方案:第 1 轮出 0,第 2、3 轮保持,第 4 轮换一次牌改出 1。

轮次小杨出牌 cᵢ我出牌aᵢ胜负(我的视角)本轮得分换牌罚分
1101输(1 胜 0)00
2102输(1 胜 0)00
32010赢(0 胜 2)2 × 10 = 200
401100赢(1 胜 0)2 × 100 = 200−b₁ = −1(第 1 次换牌)

总分 0 + 0 + 20 + 200 − 1 = 219 ✓

1
为什么"第 4 轮才换"最划算

前 3 轮出 0 几乎白送(第 1、2 轮各输 0 分),

但第 3 轮 0 刚好克 2,白赚 20 分;

把唯一的换牌花在第 4 轮(b₁ 只要 1 分),

换来 200 − 100 = 100 分的净提升。

✅ 219

2
对照几个"看起来不错"的方案

一直出 1 不换牌:1 + 2 + 0 + 200 = 203

一直出 0 不换牌:0 + 0 + 20 + 100 = 120

第 1~3 轮出 2,第 4 轮换出 1:2 + 4 + 10 + (200 − 1) = 215

一直出 2 不换牌:2 + 4 + 10 + 0 = 16

都不如 219 ✓

⚠️
注意最后那个 215:它说明"前 3 轮收益更高"并不等于"最终更好"——真正决定成败的是"换牌时机"。第 3 轮出 2 虽然能白得 10 分,却让你在第 4 轮必须再换一次牌,而第 4 轮从"出 0 换成出 1"只需要第 1 次换牌的代价(b₁ = 1)。这正是要把"换牌次数"写进状态的原因。

🧮 样例 2:N = 6,答案 56(状态的"分岔"看得最清楚)

数据:a = [3, 7, 2, 8, 9, 4],b = [1, 3, 9, 27, 81],c = [0, 1, 2, 1, 2, 0]。

1
一个最优方案:1 → 2 → 2 → 2 → 0 → 0

第 1 轮出 1 对 0:胜,2 × 3 = 6

第 2 轮换成 2 对 1:胜,2 × 7 = 14(第 1 次换牌,扣 b₁ = 1)

第 3 轮保持 2 对 2:平,得 2

第 4 轮保持 2 对 1:胜,2 × 8 = 16

第 5 轮换成 0 对 2:胜,2 × 9 = 18(第 2 次换牌,扣 b₂ = 3)

第 6 轮保持 0 对 0:平,得 4

得分合计 6 + 14 + 2 + 16 + 18 + 4 = 60,扣 1 + 3 = 4

✅ 60 − 4 = 56

2
为什么不是"每轮都换牌"

b 的后几项涨得极快:1, 3, 9, 27, 81

第 5 轮再换只花 3 分,却能多赚 18 − 9 = 9 分,划算,换;

但如果第 6 轮还想换,就要扣 b₃ = 9 分,

而第 6 轮最多也只能多赚 4 − 0 = 4 分,明显不划算。

换牌要"挑时机",这正是 DP 要搜索的东西

📊 第 3 轮结束时的两个关键状态

状态(出牌, 已换牌次数)第 3 轮结束的得分第 4 轮"换牌改出 1"的开销第 4 轮结束的得分
(出 0, 0 次)20−b₁ = −120 − 1 + 200 = 219
(出 0, 1 次)25−b₂ = −10025 − 100 + 200 = 125
(出 1, 0 次)3——(保持出 1)3 + 200 = 203
🔑
这张表是本题的灵魂:"出 0、已换 1 次"在第 3 轮结束时领先 5 分(25 比 20),看起来更优;但它输在下一轮——因为它的"下一次换牌"要扣 b₂ = 100,而"已换 0 次"的状态只要扣 b₁ = 1。
所以"当前得分高"不等于"最优",必须把换牌次数一起放进状态来比较。
04
解法对比
三维 DP vs 暴力枚举 / 贪心

⚔️ 解法对比

🟢 三维 DP + 滚动数组(推荐) 推荐

dp[出的牌][换牌次数],逐轮转移

  • 时间 O(3 · N²) = 3 × 10⁶
  • N = 1000 时约 300 万次转移
  • 空间可滚动到 O(3N)
  • 代码约 30 行
💡
两个状态维度都不能省:"出的牌"决定下一轮能否免费保持;"换牌次数"决定下一次换牌要扣 b 的哪一项。少任何一个维度,答案都会错。

🟠 暴力枚举 3^N 种出牌序列

枚举你每轮出什么牌,直接算分取最大

  • 时间 O(3^N)
  • N ≤ 15 时 3¹⁵ ≈ 1.4 × 10⁷ 尚可
  • N = 1000 时完全不可能
  • 只能拿 30% 的测试点
⚠️
量级对比:3¹⁰⁰⁰ 是个天文数字,而 3 · N² 只有 300 万。DP 的本质就是"把指数级的枚举压成多项式级的递推"。

📈 性能对比

方案复杂度可拿分数
三维 DPO(3 · N²) = 3 × 10⁶100 ✓
暴力枚举出牌序列O(3^N)30 ✓(N ≤ 15)
每轮都换牌 / 只看眼前O(N)❌ 罚分暴涨,不一定最优
05
算法流程图
逐轮转移 dp[出的牌][换牌次数]
开始读入 N、aᵢ、bᵢ、cᵢ;所有 dp 状态置为负无穷第 1 轮:dp[x][0] = score(x, c₁),自由出牌不扣分第 i 轮 = 2 … N本轮出的 c′ 与上一轮相同吗?相同 ✓保持:得分 + score(c′),换牌次数 t 不变不同 ✗换牌:得分 − b_{t+1} + score(c′),换牌次数 t → t + 1滚动:dp ← ndp(只保留上一轮的状态)所有轮次都处理完了吗?输出 max over 出的牌 x、换牌次数 t of dp[x][t]i 加一,继续下一轮
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🃏 最高得分计算器

第一行 N;第二行 a 数组;第三行 b 数组(共 N−1 个);第四行小杨的 c 数组。程序跑 DP 并回溯给出最优出牌序列。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(三维 DP + 滚动数组)

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

const long long NEG = -(1LL << 60);
long long a[1005], b[1005];
int c[1005];
long long dp[3][1005], ndp[3][1005];   // dp[我出的牌][已换牌次数]

// 我出 x、小杨出 y,第 i 轮我能得多少分
long long sc(int x, int y, int i) {
    if (x == y)                    return a[i];        // 平局:各得 a_i
    if ((x - y + 3) % 3 == 1)      return 2 * a[i];    // 取胜:得 2 * a_i
    return 0;                                          // 落败:得 0
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N;     i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= N - 1; i++) scanf("%lld", &b[i]);
    for (int i = 1; i <= N;     i++) scanf("%d",   &c[i]);

    for (int x = 0; x < 3; x++)
        for (int t = 0; t <= N - 1; t++) dp[x][t] = NEG;

    // 第 1 轮:出什么随便挑,都不算换牌
    for (int x = 0; x < 3; x++) dp[x][0] = sc(x, c[1], 1);

    for (int i = 2; i <= N; i++) {
        for (int x = 0; x < 3; x++)
            for (int t = 0; t <= N - 1; t++) ndp[x][t] = NEG;

        for (int x = 0; x < 3; x++) {
            for (int t = 0; t <= i - 2; t++) {        // 前 i-1 轮最多换 i-2 次
                if (dp[x][t] == NEG) continue;
                for (int y = 0; y < 3; y++) {
                    long long v = sc(y, c[i], i);
                    if (y == x) {                     // 保持不变:不扣分
                        ndp[y][t] = max(ndp[y][t], dp[x][t] + v);
                    } else if (t + 1 <= N - 1) {      // 换牌:扣第 t+1 次的钱
                        ndp[y][t + 1] = max(ndp[y][t + 1], dp[x][t] - b[t + 1] + v);
                    }
                }
            }
        }
        memcpy(dp, ndp, sizeof(dp));                  // 滚动
    }

    long long ans = NEG;
    for (int x = 0; x < 3; x++)
        for (int t = 0; t <= N - 1; t++) ans = max(ans, dp[x][t]);

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么"换牌"的罚分写作 b[t + 1]?因为 t 表示"已经换过 t 次",现在这一次是第 t + 1 次换牌,所以扣的正是 b_{t+1}。
罚分不是常数(b 的每一项都可能不同,样例 2 里就是 1, 3, 9, 27, 81),这正是必须把 t 写进状态的根本原因。

📖 关键几行怎么看

代码作用为什么这样写
dp[x][0] = sc(x, c[1], 1)初始化第 1 轮第 1 轮自由出牌,不扣换牌分
if (y == x) ndp[y][t] = …保持不变不付罚款,换牌次数 t 原样保留
ndp[y][t+1] = … - b[t+1] + v换牌扣的是第 t+1 次换牌的罚分
for (t = 0; t <= i - 2; t++)状态范围前 i−1 轮最多只可能换 i−2 次,越界状态不存在
memcpy(dp, ndp, sizeof(dp))滚动数组每轮只需要上一轮的状态,省掉一维
ans = max over x, t of dp[x][t]取答案最后一轮出什么牌、换了几次都不限,取最大即可
⚠️
五个坑:① 胜者得分忘记乘 2;② 罚分写成固定值(应该随次数变化);③ 第 1 轮就扣了换牌分(此时 t = 0,没有任何罚分);④ 下标错位:用了 b[t] 而不是 b[t+1];⑤ 用 int:理论上限约 2 × 10⁹,已经逼近 int 的边界,为了稳妥一律用 long long。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
1 2 10 100
1 100 1
1 1 2 0
219题面样例 1(换牌时机最关键)
6
3 7 2 8 9 4
1 3 9 27 81
0 1 2 1 2 0
56题面样例 2(罚分递增)
1
5
(第三行为空)
2
10N = 1 边界:只有第 1 轮,根本没有换牌机会
2
10 10
1000
0 1
30罚分极高:第 2 轮换牌要多赚的远少于 1000,不如保持
3
5 5 5
100 100
2 2 2
30一直出 0 专克 2,每轮得 2 × 5 = 10
4
1 1 1 1
1 100 100
0 0 1 1
7换牌有利可图:前 2 轮出 1、后 2 轮换出 2,扣 b₁ = 1
✅
自查清单:① 状态里有"换牌次数"这一维吗?② 罚分用的是 b 的第 t+1 项吗?③ 第 1 轮没扣分吧?④ 用了 long long 吗?

🚨 易错点清单

⚠️
胜者得分忘乘 2:题目规定胜者得 2 · aᵢ,平局才只得 aᵢ。
⚠️
罚分当成常数:第 t 次换牌扣的是 b_t,所以状态必须带"已换了几次"。
⚠️
第 1 轮扣分:第 1 轮是自由起点,t = 0,不产生任何罚分。
⚠️
下标错位:已经换过 t 次后,下一次换牌扣 b[t + 1]。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(3 · N²)
空间复杂度
O(3N)(滚动后)
N 最大
1000
运算量
约 3 × 10⁶

时间怎么算的?

空间都用在哪?

两个 3 × (N + 1) 的 long long 数组(dp 与 ndp),约 3 × 1000 × 8 字节 × 2 ≈ 48 KB。

✅ N = 1000 时约 300 ~ 900 万次转移,1 秒内轻松跑完。关键在于"把换牌次数放进状态"这一设计——它让"未来的罚分"变成了"当前状态的一部分"。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 状态:dp[我出的牌 x][已换牌次数 t] = 最大得分
// 转移(第 i 轮,上一轮出 x,本轮出 y):
long long v = sc(y, c[i], i);
if (y == x) ndp[y][t]   = max(ndp[y][t],   dp[x][t] + v);        // 保持
else        ndp[y][t+1] = max(ndp[y][t+1], dp[x][t] - b[t+1] + v); // 换牌

// 收益函数:平局 a_i,取胜 2 * a_i,落败 0
// 取胜判定:x 胜 y  <=>  (x - y + 3) % 3 == 1
//   1 胜 0、2 胜 1、0 胜 2 都满足这个式子

// 别忘了第 1 轮是自由起点
for (x = 0; x < 3; x++) dp[x][0] = sc(x, c[1], 1);

// 答案:最后一轮出什么、换了多少次都不限
ans = max over x, t of dp[x][t];

// 通用套路:当"未来的代价"依赖"过去做了几次某操作"时
// 就把"做了几次"写进状态(本题是换牌次数,背包题是件数,博弈题是步数)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
维度设计把"已换牌次数"写进状态,因为罚分与次数绑定任何"第 k 次操作代价不同"的题(阶梯价格、递增罚款)
滚动数组只保留上一轮的状态,空间从 O(3N²) 降到 O(3N)所有"逐层转移"的 DP(背包、路径计数、博弈)
收益函数封装把平局 / 取胜 / 落败写成一个 score 函数棋类、猜拳、对抗型模拟题的收益计算
🌟
思考题:如果题目改成"换牌不限次数,但每次换牌的罚分固定为 b"(不再区分第几次),状态还需要记换牌次数吗?(提示:不需要了——罚分不再依赖次数,状态只要 (第几轮, 当前出的牌) 两维,复杂度从 O(3 · N²) 降到 O(3N)。同一道题改了罚分规则,状态的维度就少一维——这说明"状态里该记什么",取决于"未来的收益依赖哪些历史信息"。)