华为OD机试真题 2026-9-6【少儿爬山闯关积分游戏】

少儿爬山闯关积分游戏(Java/Py/C/C++/Js/Go)题解

华为OD机试真题 新系统 华为OD上机考试真题新系统 9月6号 100分题型

华为OD机试真题新系统目录点击查看: 华为OD机试真题新系统 题库目录｜机考题库 + 算法考点详解

题目内容

山路一共设有

n

n

n 个关卡，按

1

∼

n

1 \\sim n

1∼n 顺序排列。当前位于

1

1

1 号关卡，必须按照关卡从小到大闯关，且必须到达最后第

n

n

n 号关卡才算寻宝成功。每个关卡都有对应的宝藏分值(可能为负数)，经过当前关卡即可获得该关卡分值，分数持续累加。 移动规则：

输入描述

参数1：整数

n

n

n，代表关卡数量 参数2：整数数组，依次表示第

1

∼

n

1 \\sim n

1∼n 关的宝藏分值

1

≤

n

≤

20

1 \\leq n \\leq 20

1≤n≤20 每关分值：

−

999

≤

v

a

l

≤

999

-999 \\leq val \\leq 999

−999≤val≤999

输出描述

输出一个整数，代表合法路线的最大累加得分。

样例1

输入

5
10 5 8 3 15

输出

41

说明

• 合法路线示例：$1\to 2\to 3\to 4\to 5$
• 路线 $1\to 3\to 5$

样例2

输入

4
10 1 1 100

输出

112

说明

• 路线 $1\to 2\to 3\to 4$
• 路线 $1\to 3\to 4$
• 路线 $1\to 2\to 4$
• 最大值 $112$

题解

思路：动态规划

c++

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

int solve(int n, vector<int>& a) {
// dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = a[0];
dp[0][1] = a[0];
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i–1][0], dp[i–1][1]) + a[i];
if (i > 1) {
dp[i][1] = dp[i–2][0] + a[i];
}
}
return max(dp[n–1][0], dp[n–1][1]);
}

int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << solve(n, a);
return 0;
}

Java

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

int solve(int n, vector<int>& a) {
// dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = a[0];
dp[0][1] = a[0];
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i–1][0], dp[i–1][1]) + a[i];
if (i > 1) {
dp[i][1] = dp[i–2][0] + a[i];
}
}
return max(dp[n–1][0], dp[n–1][1]);
}

int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << solve(n, a);
return 0;
}

Python

import sys

def solve(n, a):
# dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值
dp = [[0, 0] for _ in range(n)]

dp[0][0] = a[0]
dp[0][1] = a[0]

for i in range(1, n):
dp[i][0] = max(dp[i – 1][0], dp[i – 1][1]) + a[i]

if i > 1:
dp[i][1] = dp[i – 2][0] + a[i]

return max(dp[n – 1][0], dp[n – 1][1])

data = list(map(int, sys.stdin.read().split()))

n = data[0]
a = data[1:n + 1]

print(solve(n, a))

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

const input = [];

rl.on('line', line => {
input.push(line);
});

rl.on('close', () => {
const data = input.join(' ').trim().split(/\\s+/).map(Number);

const n = data[0];
const a = data.slice(1, n + 1);

console.log(solve(n, a));
});

function solve(n, a) {
// dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值
const dp = Array.from({ length: n }, () => [0, 0]);

dp[0][0] = a[0];
dp[0][1] = a[0];

for (let i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i – 1][0], dp[i – 1][1]) + a[i];

if (i > 1) {
dp[i][1] = dp[i – 2][0] + a[i];
}
}

return Math.max(dp[n – 1][0], dp[n – 1][1]);
}

Go

package main

import (
"bufio"
"fmt"
"os"
)

// 解决问题
func solve(n int, a []int) int {
// dp[i][0] 上一步跳一步最大值 dp[i][1]上一步跳两步最大值
dp := make([][2]int, n)

dp[0][0] = a[0]
dp[0][1] = a[0]

for i := 1; i < n; i++ {
if dp[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]
}

if i > 1 {
dp[i][1] = dp[i–2][0] + a[i]
}
}

if dp[n–1][0] > dp[n–1][1] {
return dp[n–1][0]
}

return dp[n–1][1]
}

func main() {
in := bufio.NewReader(os.Stdin)

var n int
fmt.Fscan(in, &n)

a := make([]int, n)

for i := 0; i < n; i++ {
fmt.Fscan(in, &a[i])
}

fmt.Println(solve(n, a))
}

C语言

#include <stdio.h>
#include <stdlib.h>

// 解决问题
int solve(int n, 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 (int i = 1; i < n; i++) {
dp[i][0] = (dp[i – 1][0] > dp[i – 1][1]
? dp[i – 1][0]
: dp[i – 1][1]) + a[i];

if (i > 1) {
dp[i][1] = dp[i – 2][0] + a[i];
}
}

int ans = dp[n – 1][0] > dp[n – 1][1]
? dp[n – 1][0]
: dp[n – 1][1];

free(dp);

return ans;
}

int main() {
int n;
scanf("%d", &n);

int *a = (int *)malloc(sizeof(int) * n);

for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}

printf("%d\\n", solve(n, a));

free(a);

return 0;
}