GESP认证C++编程真题解析 | P10108 [GESP202312 六级] 闯关游戏-育师

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

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

适合人群：

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

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

【题目来源】

洛谷：[P10108 GESP202312 六级] 闯关游戏 - 洛谷

【题目描述】

你来到了一个闯关游戏。

这个游戏总共有N NN关，每关都有M MM个通道，你需要选择一个通道并通往后续关卡。其中，第i ii个通道可以让你前进a i a_iai关，也就是说，如果你现在在第x xx关，那么选择第i ii个通道后，你将直接来到第x + a i x+a_ix+ai关（特别地，如果x + a i ≥ N x + a_i \geq Nx+ai≥N，那么你就通关了）。此外，当你顺利离开第s ss关时，你还将获得b s b_sbs分。

游戏开始时，你在第0 00关。请问，你通关时最多能获得多少总分。

【输入】

第一行两个整数N NN，M MM，分别表示关卡数量和每关的通道数量。

接下来一行M MM个用单个空格隔开的整数a 0 , a 1 ⋯ , a M − 1 a_0,a_1\cdots,a_{M-1}a0,a1⋯,aM−1。保证1 ≤ a i ≤ N 1\le a_i \le N1≤ai≤N。

接下来一行N NN个用单个空格隔开的整数b 0 , b 1 ⋯ , b N − 1 b_0,b_1\cdots,b_{N-1}b0,b1⋯,bN−1。保证∣ b i ∣ ≤ 1 0 5 |b_i|\le 10^5∣bi∣≤105。

【输出】

一行一个整数，表示你通关时最多能够获得的分数。

【输入样例】

6 2 2 3 1 0 30 100 30 30

【输出样例】

【算法标签】

《洛谷 P10108 闯关游戏》 #动态规划DP# #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;// 最大数组长度intn,m;// n: 天数, m: 药材种类数intmaxn=-1;// 最大的生长天数inta[N],b[N];// a: 药材生长天数, b: 每天可种植的药材价值intdp[N];// dp[i]: 在第i天结束时的最大总价值intmain(){// 输入药材种类数和总天数cin>>m>>n;// 输入每种药材的生长天数for(inti=1;i<=m;i++){cin>>a[i];maxn=max(maxn,a[i]);// 记录最长的生长周期}// 输入每天可种植的药材价值for(inti=1;i<=n;i++){cin>>b[i];}// 初始化dp数组为极小值memset(dp,-0x3f,sizeof(dp));dp[1]=0;// 第1天开始时，总价值为0// 动态规划// 注意：这里循环到n+maxn，因为药材可能在n天后成熟for(inti=1;i<=n+maxn;i++){for(intj=1;j<=m;j++){// 如果i-a[j]天是有效的（≥1）if(i-a[j]>=1){// 状态转移：在第i-a[j]天种植，在第i天收获dp[i]=max(dp[i],dp[i-a[j]]+b[i-a[j]]);}}}// 调试输出// for (int i=1; i<=n+maxn; i++)// cout << dp[i] << " ";// cout << endl;// 寻找最大价值// 只需要考虑n天之后到n+maxn天之间的最大值intans=-1e9;for(inti=n+1;i<=n+maxn;i++){ans=max(ans,dp[i]);}// 输出结果cout<<ans<<endl;return0;}