当前位置：首页 > GESP > （2023年GESP七级）洛谷P10111题解：动态规划求解纸牌游戏

（2023年GESP七级）洛谷P10111题解：动态规划求解纸牌游戏

4个月前 (08-17)

一、题目解读

洛谷P10111题（2023年GESP七级）是一个经典的动态规划问题，涉及循环胜负关系下的最优策略设计。题目背景可类比为“剪刀-石头-布”的循环胜负游戏：存在三种元素（如卡牌），两两之间形成循环克制关系（如0克2、1克0、2克1），玩家需通过换牌操作在多轮对决中最大化得分。题目要求处理N轮比赛，每轮可选择出牌或换牌（需消耗代价），需找到最优出牌顺序以获取最高总分。

二、解题思路

三维动态规划解决该问题。核心思路为：通过状态定义拆分决策维度，利用状态转移方程实现最优解的递推。关键在于将“换牌次数”作为独立维度，避免状态爆炸的同时精准记录代价。具体设计如下：

● 状态定义：dp[i][j][k]表示第i轮出牌j，累计换牌k次时的最大得分。

● 状态转移：分为“不换牌”与“换牌”两种情况，前者延续上一轮策略，后者需扣除换牌代价并更新出牌类型。

● 边界条件：首轮仅依赖初始牌与对手牌计算得分，后续轮次通过递推更新最优值。

三、解题步骤

1. 数据输入：读入N轮比赛的卡牌序列a、b、c（含换牌代价）。

2. 初始化DP表：首轮状态仅与初始出牌相关，调用get_score()计算平局/胜负得分。

3. 动态规划循环：

○ 外层遍历轮次i，内层遍历上一轮状态（出牌prev_j、换牌次数prev_k）。

○ 若上一状态无效（INT_MIN），跳过。

○ 不换牌：直接比较得分更新当前状态。

○ 换牌：遍历新出牌类型new_j，扣除代价b[prev_k]后计算总分，更新dp[i][new_j][prev_k+1]。

4. 结果输出：遍历最后一轮所有状态，取最大值即为最优得分。

四、代码及注释

#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;
}