这是我写的第1个正式题解

---

【A95976】[GESP202312 七级] 纸牌游戏

题目链接

点这里

题目大意

你和小杨要进行N轮游戏
每轮双方出一张牌（1赢0 2赢1 0赢2）
第i轮胜利可获得$2a_i分$，平局可获得$a_i$分，输获得$0$分
首先，游戏开始前小杨会告诉你接下来n轮的出牌
而你从第二轮开始，要么出上一轮的牌，要么换牌
如果游戏结束时你换了t次牌，就要额外扣除$b1+...+bt$分
问：最大可以获得多少分

解题思路

1. 算法选择

线性动态规划

2. 核心思路

dp定义：
$定义dp[i][j][k]为第i轮，出牌j（j \in \{1,2,3\}）,一共换了k次牌时的最大得分$

dp初始化：
第1轮需要单独初始化，只需判断是否能赢即可，并计算可得到的分数

状态转移方程：
对于每个$dp[i][j][k]$，无非就两种情况
一种是这一轮和上一轮选一样的卡牌，则$dp[i][j][k]=max(dp[i][j][k], dp[i - 1][j][k] + 当前得分)$
一种是这一轮和上一轮选不同的卡牌，并且$k \ge 1的情况$，则$dp[i][j][k] = max(dp[i][j][k], dp[i - 1][可选择的卡牌][k-1]+当前得分-b[k])$

这里大家可能有疑惑，为什么当前得分-b[k]就行了呢？题目不是说要额外扣累加起来的分数吗？
因为之前扣的分数已经在之前的状态中被扣除过了，这个状态只需要考虑本身即可。

最终答案：$\max_{\substack{0 \le j \le 2 \\ 0 \le k \le n-1}} dp[n][j][k]$

3. 复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

易错点/坑点

1. 没啥坑点，大家不要把这题想复杂了
2. 这题最重要的就是dp定义，只要把dp定义搞明白了，状态转移方程就一目了然

AC 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N = 1111;
int a[N], b[N], c[N];
int dp[N][3][N];// dp[i][j]第i轮、出j、一共换了 k 次牌时，能拿到的最大总分
// 初始化部分

int win(int my, int yang){// 1能赢，0不能赢，2平局
    if (my == 0 && yang == 1){
        return 0;
    }
    if (my == 0 && yang == 2){
        return 1;
    }
    if (my == 0 && yang == 0){
        return 2;
    }
    if (my == 1 && yang == 0){
        return 1;
    }
    if (my == 1 && yang == 2){
        return 0;
    }
    if (my == 1 && yang == 1){
        return 2;
    }
    if (my == 2 && yang == 0){
        return 0;
    }
    if (my == 2 && yang == 2){
        return 2;
    }
    if (my == 2 && yang == 1){
        return 1;
    }
}
// 判断胜利部分

signed main(){

    memset(dp, -0x3f, sizeof(dp));
    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for (int i = 1;i < n;i++){
        cin >> b[i];
        // sumb[i] = sumb[i - 1] + b[i];
    }
    for (int i = 1;i <= n;i++){
        cin >> c[i];
    }
    // 输入部分

    for (int i = 0;i < 3;i++){
        int plus = 0;
        if (win(i, c[1]) == 1){
            plus = 2 * a[1];
        }
        if (win(i, c[1]) == 2){
            plus = a[1];
        }
        dp[1][i][0] = plus;
    }
    // dp数组初始化部分

    for (int i = 2;i <= n;i++){
        for (int j = 0;j < 3;j++){
            for (int k = 0;k < n;k++){
                // 第一种情况：和上一轮选同样
                int plus = 0;
                if (win(j, c[i]) == 1){
                    plus = 2 * a[i];
                }
                if (win(j, c[i]) == 2){
                    plus = a[i];
                }
                dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + plus);
                // 第二种情况：和上一轮选不一样
                if (k == 0){
                    continue;
                }
                for (int choose = 0;choose < 3;choose++){
                    if (choose == j){
                        continue;
                    }
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][choose][k - 1] + plus - b[k]);
                }
            }
        }
    }
    // 状态转移方程部分

    int mx = INT_MIN;
    for (int i = 0;i < 3;i++){
         for (int j = 0;j < n;j++){
            mx = max(mx, dp[n][i][j]);
        }
    }
    cout << mx;
    // 求答案部分
    
    return 0;
}