GESP2023年12月认证C++七级( 第三部分编程题（2）纸牌游戏）

参考程序：

#include <iostream> 
#include <cstring>   // for memset
#include <vector>
using namespace std;

const int max_n = 1005;
int n;
int a[max_n], b[max_n], c[max_n]; // a[]: 得分系数；b[]: 换牌惩罚；c[]: 小杨的出牌

// dp[k][j] 表示用牌k，换了j次牌时的最大得分
int dp[3][max_n];

// result(x, y)：你出x，小杨出y，返回得分类型（2赢，1平，0输）
int result(int x, int y) {
    if (x == y + 1 || x == y - 2) return 2; // 赢（注意循环胜）
    if (x == y) return 1; // 平
    return 0; // 输
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;

    // 输入每轮得分系数
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // 输入换牌惩罚（从第2轮开始，到第N轮）
    for (int i = 1; i < n; ++i) cin >> b[i];

    // 输入小杨的出牌序列
    for (int i = 1; i <= n; ++i) cin >> c[i];

    // 初始化dp为极小值（负无穷），表示不可达状态
    memset(dp, 128, sizeof(dp));

    // 第1轮：你可以自由选择出哪一张牌（0、1、2）
    for (int k = 0; k < 3; ++k){
        dp[k][0] = result(k, c[1]) * a[1];  // 0次换牌
    }

    // 从第2轮开始，逐轮决策
    for (int i = 2; i <= n; ++i) {
        // 倒序遍历换牌次数，防止状态被覆盖
        for (int j = i - 1; j >= 0; --j) {
            for (int k = 0; k < 3; ++k) { // 当前想出的牌是k
                int curr_score = result(k, c[i]) * a[i];

                // 情况1：继续使用上轮的牌（没有换牌）
                dp[k][j] = dp[k][j] + curr_score;

                // 情况2：从别的牌换成牌k（消耗一次换牌机会）
                if (j > 0) {
                    for (int l = 0; l < 3; ++l) {
                        if (l == k) continue; // 不换就跳过
                        dp[k][j] = max(dp[k][j], dp[l][j - 1] + curr_score - b[j]);
                    }
                }
            }
        }
    }

    // 在所有状态中找最大值
    int ans = -2e9;
    for (int j = 0; j < n; ++j)
        for (int k = 0; k < 3; ++k) {
            ans = max(ans, dp[k][j]);
        }

    cout << ans << '\n';
    return 0;
}