自动搬运

查看原文

来自洛谷，原作者为

	WsW_ 欢迎入群872763867||题解求赞！题解看不懂请私信

搬运于2025-08-24 22:54:47，当前版本为作者最后更新于2024-01-29 23:06:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更新

这是一篇已通过的题解。

• $2025.01.20$ 改正错别字，改正手误写错的转移方程，更新部分表述。

思路

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

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

• $c_i=k$ 时，平，$add\gets a_i$。
• $(c_i+1)\bmod 3=k$ 时，赢，$add\gets 2\times a_i$。
• $(k+1)\bmod 3=c_i$ 时，输，$add\gets 0$。

再考虑有几种转移路径。

• 不换牌。那么说明第 $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;
}