GESP认证C++编程真题解析 | P10111 [GESP202312 七级] 纸牌游戏

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[P10111 GESP202312 七级] 纸牌游戏 - 洛谷

【题目描述】

你和小杨在玩一个纸牌游戏。

你和小杨各有3 33张牌，分别是0 、 1 、 2 0、1、20、1、2。你们要进行N NN轮游戏，每轮游戏双方都要出一张牌，并按1 11战胜0 00，2 22战胜1 11，0 00战胜2 22的规则决出胜负。第i ii轮的胜者可以获得2 × a i 2 \times a_i2×ai​分，败者不得分，如果双方出牌相同，则算平局，二人都可获得a i a_iai​分( i = 1 , 2 , ⋯ , N ) (i=1,2,\cdots,N)(i=1,2,⋯,N)。

玩了一会后，你们觉得这样太过于单调，于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部n nn轮的出牌，并将他的全部计划告诉你；而你从第2 22轮开始，要么继续出上一轮出的牌，要么记一次“换牌”。游戏结束时，你换了t tt次牌，就要额外扣b 1 + ⋯ + b t b_1+\cdots+b_tb1​+⋯+bt​分。

请计算出你最多能获得多少分。

【输入】

第一行一个整数N NN，表示游戏轮数。

第二行N NN个用单个空格隔开的非负整数a 1 , ⋯ , a N a_1,\cdots,a_Na1​,⋯,aN​，意义见题目描述。

第三行N − 1 N-1N−1个用单个空格隔开的非负整数b 1 , ⋯ , b N − 1 b_1,\cdots,b_{N-1}b1​,⋯,bN−1​，表示换牌的罚分，具体含义见题目描述。由于游戏进行 N 轮，所以你至多可以换N − 1 N-1N−1次牌。

第四行N NN个用单个空格隔开的整数c 1 , ⋯ , c N c_1,\cdots,c_Nc1​,⋯,cN​，依次表示小杨从第1 11轮至第N NN轮出的牌。保证c i ∈ 0 , 1 , 2 c_i\in{0,1,2}ci​∈0,1,2。

【输出】

一行一个整数，表示你最多获得的分数。

【输入样例】

4 1 2 10 100 1 100 1 1 1 2 0

【输出样例】

219

【算法标签】

《洛谷 P10111 纸牌游戏》 #动态规划DP# #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1005;// 最大轮数intn;// 总轮数intans=-1e9;// 最终答案inta[N],b[N],c[N];// a: 每轮基础得分, b: 换牌代价, c: 每轮出牌类型intdp[N][N][3];// dp[i][j][k]: 前i轮换了j次牌，第i轮出牌类型为k的最大得分// 计算在第pos轮，上次出牌类型x，本次出牌类型y的得分intcalc(intx,inty,intpos){if(x==y)// 两次出牌类型相同{returna[pos];// 得a[pos]分}if(x==0)// 上次出石头{if(y==1)// 这次出布{return0;// 平局}else// 这次出剪刀{return2*a[pos];// 获胜}}elseif(x==1)// 上次出布{if(y==0)// 这次出石头{return2*a[pos];// 获胜}else// 这次出剪刀{return0;// 平局}}else// 上次出剪刀{if(y==0)// 这次出石头{return0;// 平局}else// 这次出布{return2*a[pos];// 获胜}}}intmain(){// 输入cin>>n;for(inti=1;i<=n;i++)// 每轮基础得分{cin>>a[i];}for(inti=1;i<n;i++)// 第i次换牌的代价{cin>>b[i];}for(inti=1;i<=n;i++)// 第i轮必须出的牌型{cin>>c[i];}// 初始化dp为极小值memset(dp,0,sizeof(dp));// 实际为0，但代码中未显示初始化// 动态规划for(inti=1;i<=n;i++)// 枚举轮数{for(intj=0;j<i;j++)// 枚举换牌次数{for(intk=0;k<=2;k++)// 枚举当前轮实际出牌类型{// 计算当前轮得分intx=calc(k,c[i],i);// 不换牌的情况dp[i][j][k]=dp[i-1][j][k]+x;// 如果j=0，不能换牌if(j==0)continue;// 逻辑检查：第i轮最多换i-1次牌if(j==i-1){dp[i][j][k]=-1e9;// 标记为不可能}// 换牌的情况if(k==0)// 当前出石头{dp[i][j][k]=max(dp[i][j][k],max(dp[i-1][j-1][1],dp[i-1][j-1][2])-b[j]+x);}elseif(k==1)// 当前出布{dp[i][j][k]=max(dp[i][j][k],max(dp[i-1][j-1][0],dp[i-1][j-1][2])-b[j]+x);}else// 当前出剪刀{dp[i][j][k]=max(dp[i][j][k],max(dp[i-1][j-1][0],dp[i-1][j-1][1])-b[j]+x);}}}}// 找最大值for(inti=0;i<n;i++){ans=max({ans,dp[n][i][0],dp[n][i][1],dp[n][i][2]});}// 输出结果cout<<ans<<endl;return0;}

【运行结果】

4 1 2 10 100 1 100 1 1 1 2 0 219