题解：P10111 [GESP202312 七级] 纸牌游戏

WsW_ · 2024-01-29 23:06:28 · 题解

更新

这是一篇已通过的题解。

思路

因为游戏一轮一轮地进行，所以考虑 dp。
定义 dp_{i,j,k} 表示游戏进行到第 i 轮，此时已经换了 j 次牌，当前手牌为 k 的最大分数。

记第 i 轮出 k 可以获得 add 分。
观察题面规律，

再考虑有几种转移路径。

• 不换牌。那么说明第 i-1 轮即上一轮，出的也是 k。dp_{i,j,k}=dp_{i-1,j,k}+add。
• 换牌。那么说明第 i-1 轮即上一轮，出的是 (k+1)\bmod3 或 (k+2)\bmod3。dp_{i,j,k}=\max(dp_{i-1,j-1,(k+1)\bmod3},dp_{i-1,j-1,(k+2)\bmod3})。

根据题意，第 1 轮必定不换牌。
所以，在 i 轮中最多换牌 i-1 次，当 j=i-1 时一定是每一轮都换了牌，上一轮就必定换了牌。

需要枚举 n 轮，每轮 n-1 种换牌情况，每种换牌情况可能有 3 种出牌。
故时间复杂度为 O(n^2)。

代码

#include<bits/stdc++.h>
using namespace std;

int n;
int a[1003],b[1003],c[1003];
int dp[1003][1003][3];//dp[i][j][k]：进行到第i轮，换了j次牌，牌为k的最大得分 
int ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++){//枚举轮 
        for(int j=0;j<i;j++){//枚举本轮换牌次数（到第i轮最多换了i-1次牌） 
            for(int k=0;k<3;k++){//枚举出的牌 
                int add=0,tt=-2e9;
                if((c[i]+1)%3==k)add=(a[i]<<1);//赢 
                if(c[i]==k)add=a[i];//平 
                if(j<i-1||i==1)tt=max(tt,dp[i-1][j][k]);//不换牌 
                if(j>0)tt=max(tt,max(dp[i-1][j-1][(k+1)%3],dp[i-1][j-1][(k+2)%3])-b[j]);//换牌 
                dp[i][j][k]=tt+add;//加上这局的分 
            }
        }
    }
    for(int i=0;i<n;i++){
        ans=max({ans,dp[n][i][0],dp[n][i][1],dp[n][i][2]});
    }
    cout<<ans;
    return 0;
}