少儿爬山闯关积分游戏(Java/Py/C/C/Js/Go)题解华为OD机试真题 新系统 华为OD上机考试真题新系统 9月6号 100分题型华为OD机试真题新系统目录点击查看: 华为OD机试真题新系统 题库目录机考题库 算法考点详解题目内容山路一共设有n nn个关卡按1 ∼ n 1 \sim n1∼n顺序排列。当前位于1 11号关卡必须按照关卡从小到大闯关且必须到达最后第n nn号关卡才算寻宝成功。每个关卡都有对应的宝藏分值(可能为负数)经过当前关卡即可获得该关卡分值分数持续累加。移动规则从当前关卡下一次只能在前方1 11关或者2 22关处打卡限制规则不能连续两次都一次性跳2 22关违反该规则的路线无效请求出所有合法路线中能够收集到的最大累加总分。输入描述参数1整数n nn代表关卡数量参数2整数数组依次表示第1 ∼ n 1 \sim n1∼n关的宝藏分值1 ≤ n ≤ 20 1 \leq n \leq 201≤n≤20每关分值− 999 ≤ v a l ≤ 999 -999 \leq val \leq 999−999≤val≤999输出描述输出一个整数代表合法路线的最大累加得分。样例1输入5 10 5 8 3 15输出41说明合法路线示例1 → 2 → 3 → 4 → 5 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 51→2→3→4→5无连续跳两关总分10 5 8 3 15 41 1058315 41105831541路线1 → 3 → 5 1 \rightarrow 3 \rightarrow 51→3→5连续两次跳2 22关违规不计入统计。样例2输入4 10 1 1 100输出112说明路线1 → 2 → 3 → 4 1 \rightarrow 2 \rightarrow 3 \rightarrow 41→2→3→4( 1 , 1 , 1 ) (1,1,1)(1,1,1):10 1 1 100 112 10111001121011100112路线1 → 3 → 4 1 \rightarrow 3 \rightarrow 41→3→4( 2 , 1 ) (2,1)(2,1):10 1 100 111 101100111101100111路线1 → 2 → 4 1 \rightarrow 2 \rightarrow 41→2→4( 1 , 2 ) (1,2)(1,2):10 1 100 111 101100111101100111最大值112 112112。题解思路动态规划定义dp[][2]数组其中dp[i][0]到达 i最后一步跳 1 格能取到的最大总分其中dp[i][1]到达 i最后一步跳 2格能取到的最大总分当前到达位置i进行状态过程为:只跳一步到达i-1 - i, 可以从上个位置跳一次和跳两次转移所以dp[i][0] max(dp[i-1][0], dp[i-1][1]) a[i]跳两步到达i-2 - i, 只能从i-2位置跳一次转移所以dp[i][1] dp[i-2][0] a[i];最终能取到的最大总分为max(dp[n-1][0], dp[n-1][1])c#includebits/stdc.h#includevectorusingnamespacestd;intsolve(intn,vectorinta){// dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值vectorvectorintdp(n,vectorint(2,0));dp[0][0]a[0];dp[0][1]a[0];for(inti1;in;i){dp[i][0]max(dp[i-1][0],dp[i-1][1])a[i];if(i1){dp[i][1]dp[i-2][0]a[i];}}returnmax(dp[n-1][0],dp[n-1][1]);}intmain(){intn;cinn;vectorinta(n);for(inti0;in;i){cina[i];}coutsolve(n,a);return0;}Java#includebits/stdc.h#includevectorusing namespace std;intsolve(intn,vectorinta){// dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值vectorvectorintdp(n,vectorint(2,0));dp[0][0]a[0];dp[0][1]a[0];for(inti1;in;i){dp[i][0]max(dp[i-1][0],dp[i-1][1])a[i];if(i1){dp[i][1]dp[i-2][0]a[i];}}returnmax(dp[n-1][0],dp[n-1][1]);}intmain(){intn;cinn;vectorinta(n);for(inti0;in;i){cina[i];}coutsolve(n,a);return0;}Pythonimportsysdefsolve(n,a):# dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值dp[[0,0]for_inrange(n)]dp[0][0]a[0]dp[0][1]a[0]foriinrange(1,n):dp[i][0]max(dp[i-1][0],dp[i-1][1])a[i]ifi1:dp[i][1]dp[i-2][0]a[i]returnmax(dp[n-1][0],dp[n-1][1])datalist(map(int,sys.stdin.read().split()))ndata[0]adata[1:n1]print(solve(n,a))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(line);});rl.on(close,(){constdatainput.join( ).trim().split(/\s/).map(Number);constndata[0];constadata.slice(1,n1);console.log(solve(n,a));});functionsolve(n,a){// dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值constdpArray.from({length:n},()[0,0]);dp[0][0]a[0];dp[0][1]a[0];for(leti1;in;i){dp[i][0]Math.max(dp[i-1][0],dp[i-1][1])a[i];if(i1){dp[i][1]dp[i-2][0]a[i];}}returnMath.max(dp[n-1][0],dp[n-1][1]);}Gopackagemainimport(bufiofmtos)// 解决问题funcsolve(nint,a[]int)int{// dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值dp:make([][2]int,n)dp[0][0]a[0]dp[0][1]a[0]fori:1;in;i{ifdp[i-1][0]dp[i-1][1]{dp[i][0]dp[i-1][0]a[i]}else{dp[i][0]dp[i-1][1]a[i]}ifi1{dp[i][1]dp[i-2][0]a[i]}}ifdp[n-1][0]dp[n-1][1]{returndp[n-1][0]}returndp[n-1][1]}funcmain(){in:bufio.NewReader(os.Stdin)varnintfmt.Fscan(in,n)a:make([]int,n)fori:0;in;i{fmt.Fscan(in,a[i])}fmt.Println(solve(n,a))}C语言#includestdio.h#includestdlib.h// 解决问题intsolve(intn,int*a){// dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值int(*dp)[2](int(*)[2])calloc(n,sizeof(int[2]));dp[0][0]a[0];dp[0][1]a[0];for(inti1;in;i){dp[i][0](dp[i-1][0]dp[i-1][1]?dp[i-1][0]:dp[i-1][1])a[i];if(i1){dp[i][1]dp[i-2][0]a[i];}}intansdp[n-1][0]dp[n-1][1]?dp[n-1][0]:dp[n-1][1];free(dp);returnans;}intmain(){intn;scanf(%d,n);int*a(int*)malloc(sizeof(int)*n);for(inti0;in;i){scanf(%d,a[i]);}printf(%d\n,solve(n,a));free(a);return0;}