#P3200. 跳格子2(200分)
-
1000ms
Tried: 92
Accepted: 36
Difficulty: 4
所属公司 :
华为od
跳格子2(200分)
题面描述
小明和朋友玩跳格子游戏,有 n 个连续格子组成的圆圈,每个格子有不同的分数。小朋友可以选择从任意格子起跳,但在跳跃过程中:
- 不能跳到连续的格子。
- 不能回头跳。
- 不能超过一圈(即不能回到起点)。
给定一个代表每个格子得分的非负整数数组,计算能够得到的最高分数。
思路
这道题类似于经典的“打家劫舍”问题(House Robber),但增加了圆形排列的限制。由于格子是首尾相连的,选择第一个格子和最后一个格子会导致相邻,因此我们需要考虑两种情况:
- 包含第一个格子,排除最后一个格子:即计算从第一个格子到倒数第二个格子的最大得分。
- 排除第一个格子,包含最后一个格子:即计算从第二个格子到最后一个格子的最大得分。
最终结果取这两种情况的最大值。
代码分析
我们可以定义一个辅助函数 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