这是我写的第1个正式题解
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
【A95976】[GESP202312 七级] 纸牌游戏
题目链接
点这里
题目大意
你和小杨要进行N轮游戏
每轮双方出一张牌（1赢0 2赢1 0赢2）
第i轮胜利可获得2ai分2a_i分2ai 分，平局可获得aia_iai 分，输获得000分
首先，游戏开始前小杨会告诉你接下来n轮的出牌
而你从第二轮开始，要么出上一轮的牌，要么换牌
如果游戏结束时你换了t次牌，就要额外扣除b1+...+btb1+...+btb1+...+bt分
问：最大可以获得多少分
解题思路
1. 算法选择
线性动态规划
2. 核心思路
> dp定义：
> 定义dp[i][j][k]为第i轮，出牌j（j∈{1,2,3}）,一共换了k次牌时的最大得分定义dp[i][j][k]为第i轮，出牌j（j \in \{1,2,3\}）,一共换了k次牌时的最大得分定义dp[i][j][k]为第i轮，出牌j（j∈{1,2,3}）,一共换了k次牌时的最大得分
> dp初始化：
> 第1轮需要单独初始化，只需判断是否能赢即可，并计算可得到的分数
> 状态转移方程：
> 对于每个dp[i][j][k]dp[i][j][k]dp[i][j][k]，无非就两种情况
> 一种是这一轮和上一轮选一样的卡牌，则dp[i][j][k]=max(dp[i][j][k],dp[i−1][j][k]+当前得分)dp[i][j][k]=max(dp[i][j][k], dp[i - 1][j][k] + 当前得分)dp[i][j][k]=max(dp[i][j][k],dp[i−1][j][k]+当前得分)
> 一种是这一轮和上一轮选不同的卡牌，并且k≥1的情况k \ge 1的情况k≥1的情况，则dp[i][j][k]=max(dp[i][j][k],dp[i−1][可选择的卡牌][k−1]+当前得分−b[k])dp[i][j][k] = max(dp[i][j][k], dp[i - 1][可选择的卡牌][k-1]+当前得分-b[k])dp[i][j][k]=max(dp[i][j][k],dp[i−1][可选择的卡牌][k−1]+当前得分−b[k])
这里大家可能有疑惑，为什么当前得分-b[k]就行了呢？题目不是说要额外扣累加起来的分数吗？
因为之前扣的分数已经在之前的状态中被扣除过了，这个状态只需要考虑本身即可。
> 最终答案：max0≤j≤20≤k≤n−1dp[n][j][k]\max_{\substack{0 \le j \le 2 \\ 0 \le k \le n-1}} dp[n][j][k]max0≤j≤20≤k≤n−1 dp[n][j][k]
3. 复杂度分析
* 时间复杂度：O(n2)O(n^2)O(n2)
* 空间复杂度：O(n2)O(n^2)O(n2)
易错点/坑点
1. 没啥坑点，大家不要把这题想复杂了
2. 这题最重要的就是dp定义，只要把dp定义搞明白了，状态转移方程就一目了然
AC 代码
