题面描述

小明和朋友玩跳格子游戏，有 $n$ 个连续格子组成的圆圈，每个格子有不同的分数。小朋友可以选择从任意格子起跳，但在跳跃过程中：

• 不能跳到连续的格子。
• 不能回头跳。
• 不能超过一圈（即不能回到起点）。

给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数。

思路

这道题类似于经典的“打家劫舍”问题（House Robber），但增加了圆形排列的限制。由于格子是首尾相连的，选择第一个格子和最后一个格子会导致相邻，因此我们需要考虑两种情况：

1. 包含第一个格子，排除最后一个格子：即计算从第一个格子到倒数第二个格子的最大得分。
2. 排除第一个格子，包含最后一个格子：即计算从第二个格子到最后一个格子的最大得分。

最终结果取这两种情况的最大值。

代码分析

我们可以定义一个辅助函数 rob_linear 来计算线性排列中最大得分，遵循以下规则：

• 对于每个格子，有两种选择：跳到该格子或不跳。
• 如果选择跳到该格子，则不能跳到相邻的格子。
• 使用动态规划记录到当前格子的最大得分。

在主函数中，根据上述两种情况调用 rob_linear，然后取最大值作为最终结果。

cpp

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

// 辅助函数：计算线性排列中不相邻元素的最大和
int rob_linear(vector<int>& nums, int start, int end){
    if(start > end) return 0;
    // dp[i] 表示到第i个格子的最大得分
    vector<int> dp(end - start + 2, 0);
    dp[0] = 0;
    dp[1] = nums[start];
    for(int i = 2; i <= end - start + 1; ++i){
        dp[i] = max(dp[i-1], dp[i-2] + nums[start + i - 1]);
    }
    return dp[end - start + 1];
}

int main(){
    // 读取输入
    string s;
    getline(cin, s);
    vector<int> nums;
    int num;
    stringstream ss(s);
    while(ss >> num){
        nums.push_back(num);
    }
    int n = nums.size();
    if(n == 0){
        cout << 0;
        return 0;
    }
    if(n == 1){
        cout << nums[0];
        return 0;
    }
    // 情况1：包含第一个格子，排除最后一个格子
    int case1 = rob_linear(nums, 0, n-2);
    // 情况2：排除第一个格子，包含最后一个格子
    int case2 = rob_linear(nums, 1, n-1);
    // 取两者的最大值
    cout << max(case1, case2);
    return 0;
}

python

def rob_linear(nums, start, end):
    if start > end:
        return 0
    dp = [0] * (end - start + 2)
    dp[0] = 0
    dp[1] = nums[start]
    for i in range(2, end - start + 2):
        dp[i] = max(dp[i-1], dp[i-2] + nums[start + i - 1])
    return dp[end - start + 1]

def main():
    import sys
    s = sys.stdin.read()
    nums = list(map(int, s.strip().split()))
    n = len(nums)
    if n == 0:
        print(0)
        return
    if n == 1:
        print(nums[0])
        return
    # 情况1：包含第一个格子，排除最后一个格子
    case1 = rob_linear(nums, 0, n-2)
    # 情况2：排除第一个格子，包含最后一个格子
    case2 = rob_linear(nums, 1, n-1)
    # 取两者的最大值
    print(max(case1, case2))

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    // 辅助函数：计算线性排列中不相邻元素的最大和
    public static int robLinear(int[] nums, int start, int end){
        if(start > end) return 0;
        int n = end - start + 1;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[start];
        for(int i = 2; i <= n; i++){
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[start + i - 1]);
        }
        return dp[n];
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] parts = s.trim().split("\\s+");
        int n = parts.length;
        if(n == 0){
            System.out.println(0);
            return;
        }
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) nums[i] = Integer.parseInt(parts[i]);
        if(n == 1){
            System.out.println(nums[0]);
            return;
        }
        // 情况1：包含第一个格子，排除最后一个格子
        int case1 = robLinear(nums, 0, n-2);
        // 情况2：排除第一个格子，包含最后一个格子
        int case2 = robLinear(nums, 1, n-1);
        // 取两者的最大值
        System.out.println(Math.max(case1, case2));
    }
}

题目描述

小明和朋友玩跳格子游戏，有 $n$ 个连续格子组成的圆圈，每个格子有不同的分数，小朋友可以选择以任意格子起跳，但是不能跳连续的格子，不能回头跳，也不能超过一圈;

给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数。

输入描述

给定一个数例，第一个格子和最后一个格子首尾相连，如: $2$ $3$ $2$

输出描述

输出能够得到的最高分，如: $3$

备注

$1 ≤ nums.length ≤ 100$

$1 ≤ nums[i] ≤ 1000$

样例1

输入

2 3 2

输出

3

说明

只能跳 $3$ 这个格子，因为第一个格子和第三个格子首尾相连

样例2

输入

1 2 3 1

输出

4

说明

$1 + 3 = 4$