小杨 N 轮出牌已知;你每轮"保持不变"或"换牌",换 t 次扣 b₁+…+b_t 分,求最多得分。
你和小杨各有三张牌: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[i][x][t]:前 i 轮、第 i 轮出的牌是 x、累计已换牌 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 |
t 从 0 开始2 · aᵢ,这正是"平局(各得 aᵢ)"与"取胜(得 2 · aᵢ)"的差别所在,写收益函数时最容易漏掉这个 2数据:a = [1, 2, 10, 100],b = [1, 100, 1],c = [1, 1, 2, 0]。
最优方案:第 1 轮出 0,第 2、3 轮保持,第 4 轮换一次牌改出 1。
| 轮次 | 小杨出牌 cᵢ | 我出牌 | aᵢ | 胜负(我的视角) | 本轮得分 | 换牌罚分 |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 输(1 胜 0) | 0 | 0 |
| 2 | 1 | 0 | 2 | 输(1 胜 0) | 0 | 0 |
| 3 | 2 | 0 | 10 | 赢(0 胜 2) | 2 × 10 = 20 | 0 |
| 4 | 0 | 1 | 100 | 赢(1 胜 0) | 2 × 100 = 200 | −b₁ = −1(第 1 次换牌) |
总分 0 + 0 + 20 + 200 − 1 = 219 ✓
前 3 轮出 0 几乎白送(第 1、2 轮各输 0 分),
但第 3 轮 0 刚好克 2,白赚 20 分;
把唯一的换牌花在第 4 轮(b₁ 只要 1 分),
换来 200 − 100 = 100 分的净提升。
✅ 219
一直出 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 ✓
数据:a = [3, 7, 2, 8, 9, 4],b = [1, 3, 9, 27, 81],c = [0, 1, 2, 1, 2, 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
b 的后几项涨得极快:1, 3, 9, 27, 81
第 5 轮再换只花 3 分,却能多赚 18 − 9 = 9 分,划算,换;
但如果第 6 轮还想换,就要扣 b₃ = 9 分,
而第 6 轮最多也只能多赚 4 − 0 = 4 分,明显不划算。
换牌要"挑时机",这正是 DP 要搜索的东西
| 状态(出牌, 已换牌次数) | 第 3 轮结束的得分 | 第 4 轮"换牌改出 1"的开销 | 第 4 轮结束的得分 |
|---|---|---|---|
| (出 0, 0 次) | 20 | −b₁ = −1 | 20 − 1 + 200 = 219 |
| (出 0, 1 次) | 25 | −b₂ = −100 | 25 − 100 + 200 = 125 |
| (出 1, 0 次) | 3 | ——(保持出 1) | 3 + 200 = 203 |
dp[出的牌][换牌次数],逐轮转移
枚举你每轮出什么牌,直接算分取最大
| 方案 | 复杂度 | 可拿分数 |
|---|---|---|
| 三维 DP | O(3 · N²) = 3 × 10⁶ | 100 ✓ |
| 暴力枚举出牌序列 | O(3^N) | 30 ✓(N ≤ 15) |
| 每轮都换牌 / 只看眼前 | O(N) | ❌ 罚分暴涨,不一定最优 |
第一行 N;第二行 a 数组;第三行 b 数组(共 N−1 个);第四行小杨的 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}。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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] | 取答案 | 最后一轮出什么牌、换了几次都不限,取最大即可 |
b[t] 而不是 b[t+1];⑤ 用 int:理论上限约 2 × 10⁹,已经逼近 int 的边界,为了稳妥一律用 long long。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 219 | 题面样例 1(换牌时机最关键) |
6 | 56 | 题面样例 2(罚分递增) |
1 | 10 | N = 1 边界:只有第 1 轮,根本没有换牌机会 |
2 | 30 | 罚分极高:第 2 轮换牌要多赚的远少于 1000,不如保持 |
3 | 30 | 一直出 0 专克 2,每轮得 2 × 5 = 10 |
4 | 7 | 换牌有利可图:前 2 轮出 1、后 2 轮换出 2,扣 b₁ = 1 |
2 · aᵢ,平局才只得 aᵢ。b_t,所以状态必须带"已换了几次"。t = 0,不产生任何罚分。b[t + 1]。两个 3 × (N + 1) 的 long long 数组(dp 与 ndp),约 3 × 1000 × 8 字节 × 2 ≈ 48 KB。
✅ N = 1000 时约 300 ~ 900 万次转移,1 秒内轻松跑完。关键在于"把换牌次数放进状态"这一设计——它让"未来的罚分"变成了"当前状态的一部分"。
// 状态: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 函数 | 棋类、猜拳、对抗型模拟题的收益计算 |
(第几轮, 当前出的牌) 两维,复杂度从 O(3 · N²) 降到 O(3N)。同一道题改了罚分规则,状态的维度就少一维——这说明"状态里该记什么",取决于"未来的收益依赖哪些历史信息"。)