18. 少儿爬山闯关积分游戏

题目内容

山路一共设有 n 个关卡，按 1 ∼ n 顺序排列。当前位于 1 号关卡，必须按照关卡从小到大闯关，且必须到达最后第 n 号关卡才算寻宝成功。每个关卡都有对应的宝藏分值（可能为负数），经过当前关卡即可获得该关卡分值，分数持续累加。

移动规则：

• 从当前关卡，下一次只能在前方 1 关或者 2 关处打卡；
• 限制规则：不能连续两次都一次性跳 2 关，违反该规则的路线无效；

请求出：所有合法路线中，能够收集到的最大累加总分。

输入描述

• 参数 1：整数 n，代表关卡数量
• 参数 2：整数数组，依次表示第 1 ∼ n 关的宝藏分值
• 1 ≤ n ≤ 20
• 每关分值：−999 ≤ val ≤ 999

输出描述

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

样例

样例 1

输入

5
10 5 8 3 15

输出

41

说明：

• 合法路线示例：1→2→3→4→5，无连续跳两关，总分：10+5+8+3+15=41
• 路线 1→3→5 连续两次跳 2 关，违规，不计入统计。

样例 2

输入

4
10 1 1 100

输出

112

说明：

• 路线 1→2→3→4（1,1,1）：10+1+1+100=112
• 路线 1→3→4（2,1）：10+1+100=111
• 路线 1→2→4（1,2）：10+1+100=111

最大值 112。

代码

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

rl.on('line', (input) => {
    const n = Number(input);
    rl.on('line', (input) => {
        let max = -Infinity;
        const arr = input.split(' ').map(Number);
        if (n === 1) {
            console.log(arr[0]);
            return;
        }
        const dfs = (i, lastJumpTwo, sum) => {
            if (i === n - 1) {
                max = Math.max(max, sum);
                return;
            }
            // 走1步
            if (i + 1 < n) {
                dfs(i + 1, false, sum + arr[i + 1]);
            }
            // 走2步，前提是上一次不是跳2步来的
            if (!lastJumpTwo && i + 2 < n) {
                dfs(i + 2, true, sum + arr[i + 2]);
            }
        };

        dfs(0, false, arr[0]);
        console.log(max);
    })
})

或者

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

let lineCount = 0;
let n, arr;

rl.on('line', (input) => {
    if (lineCount === 0) {
        n = Number(input);
        lineCount++;
    } else {
        arr = input.split(' ').map(Number);
        
        // 边界：只有1关
        if (n === 1) {
            console.log(arr[0]);
            rl.close();
            return;
        }
        
        // dp[i][0]: 到第i关，上一步走1关
        // dp[i][1]: 到第i关，上一步跳2关
        // 初始化负无穷，表示不可达
        const dp = Array.from({ length: n }, () => [-Infinity, -Infinity]);
        
        // 第0关（第1关）：初始就在这里，没有"上一步"
        // 可以理解为"上一步走1关"到达起点
        dp[0][0] = arr[0];
        dp[0][1] = -Infinity; // 不可能跳2关到起点
        
        // 第1关（第2关）
        if (n >= 2) {
            // 只能从第0关走1关来
            dp[1][0] = dp[0][0] + arr[1];
            // 不能从-1关跳2关来
            dp[1][1] = -Infinity;
        }
        
        // 从第2关开始递推
        for (let i = 2; i < n; i++) {
            // 上一步走1关：可以从i-1走1或跳2来，取最大
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]) + arr[i];
            
            // 上一步跳2关：只能从i-2走1关来（不能从i-2跳2关来，否则连续两次跳2）
            dp[i][1] = dp[i-2][0] + arr[i];
        }
        
        // 答案是到达最后一关的两种状态的最大值
        const result = Math.max(dp[n-1][0], dp[n-1][1]);
        console.log(result);
        rl.close();
    }
});