动态规划实战：洛谷P10111（2023GESP七级）纸牌游戏
一、问题理解与建模
这道题目描述了一个特殊的纸牌游戏：
双方各有0、1、2三张牌
游戏进行N轮，每轮双方出牌
胜负规则：1胜0，2胜1，0胜2
得分规则：
胜者得2×aᵢ分
败者不得分
平局各得aᵢ分
特殊规则：
对手的出牌顺序已知
玩家从第2轮开始，要么保持上一轮的牌，要么换牌（有换牌惩罚）
我们需要计算玩家能获得的最大分数，考虑换牌的惩罚。
二、算法选择
这是一个典型的动态规划问题，因为：
问题可以分解为子问题（每轮的选择）
有重叠子问题（相同的状态会重复出现）
有最优子结构（全局最优解包含局部最优解）
我们定义DP[i][j][k]表示：
进行到第i轮
当前出牌为j
已经换牌k次
时的最大得分。
三、完整代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// 判断胜负关系，返回得分
int get_score(int my_card, int yang_card, int a) {
if (my_card == yang_card) return a; // 平局
if ((my_card == 1 && yang_card == 0) ||
(my_card == 2 && yang_card == 1) ||
(my_card == 0 && yang_card == 2)) {
return 2 * a; // 获胜
}
return 0; // 失败
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> a(N), b(N-1), c(N);
for (int i = 0; i < N; ++i) cin >> a[i];
for (int i = 0; i < N-1; ++i) cin >> b[i];
for (int i = 0; i < N; ++i) cin >> c[i];
// dp[i][j][k]: 第i轮出牌j，换了k次牌的最大得分
vector<vector<vector<int>>> dp(N, vector<vector<int>>(3, vector<int>(N, INT_MIN)));
// 初始化第一轮
for (int j = 0; j < 3; ++j) {
dp[0][j][0] = get_score(j, c[0], a[0]);
}
// 动态规划
for (int i = 1; i < N; ++i) {
for (int prev_j = 0; prev_j < 3; ++prev_j) {
for (int prev_k = 0; prev_k < N; ++prev_k) {
if (dp[i-1][prev_j][prev_k] == INT_MIN) continue;
// 不换牌
int score = get_score(prev_j, c[i], a[i]);
if (dp[i][prev_j][prev_k] < dp[i-1][prev_j][prev_k] + score) {
dp[i][prev_j][prev_k] = dp[i-1][prev_j][prev_k] + score;
}
// 换牌（不能超过N-1次）
if (prev_k < N-1) {
for (int new_j = 0; new_j < 3; ++new_j) {
if (new_j == prev_j) continue;
score = get_score(new_j, c[i], a[i]);
int new_score = dp[i-1][prev_j][prev_k] + score - b[prev_k];
if (dp[i][new_j][prev_k+1] < new_score) {
dp[i][new_j][prev_k+1] = new_score;
}
}
}
}
}
}
// 找出最大得分
int max_score = INT_MIN;
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < N; ++k) {
max_score = max(max_score, dp[N-1][j][k]);
}
}
cout << max_score << endl;
return 0;
}原创内容 转载请注明出处
