题目描述

给定一个长度为 n 的整型数组，表示一个选手在 n 轮内可选择的牌面分数。

选手基于规则选牌，请计算所有轮结束后其可以获得的最高总分数。

选择规则：

1. 选择当前轮牌面：总分数加上该轮的分数。
2. 跳过当前轮牌面：总分数恢复到三轮前的总分数。如果当前轮次小于等于3轮，跳过时总分数为0。

选手的初始总分数为 0，且必须依次参加每一轮。

解题思路

这个问题可以通过动态规划来解决。我们需要定义一个状态 dp[i]，表示在第 i 轮结束时，选手能够获得的最高总分数。

状态定义：

• dp[i]：表示在第 i 轮结束时，选手能够获得的最高总分数。

状态转移方程：

在第 i 轮，选手有两种选择：

1. 选择当前轮牌面：
   • 总分数为 dp[i-1] + scores[i]。
2. 跳过当前轮牌面：
   • 总分数恢复为 dp[i-3]。
   • 如果 i < 3，则总分数恢复为 0。

因此，状态转移方程为：

dp[i] = max(dp[i-1] + scores[i], dp[i-3] if i >= 3 else 0)

初始化：

• dp[0] = max(scores[0], 0)：在第一轮，可以选择拿分数或跳过（得到0）。
• 对于 i = 1 和 i = 2：
  • dp[i] = max(dp[i-1] + scores[i], 0)

最终答案：

最终答案为 dp[n-1]，即所有轮结束后的最高总分数。

cpp

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

int main() {
    string input;
    getline(cin, input);  // 读取输入字符串
    
    // 将输入字符串转换为数组
    stringstream ss(input);
    string token;
    vector<int> scores;
    while (getline(ss, token, ',')) {
        scores.push_back(stoi(token));
    }
    
    int n = scores.size();
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    vector<int> dp(n, 0);
    
    // 初始化 dp[0]
    dp[0] = max(scores[0], 0);
    
    // 初始化 dp[1] 和 dp[2]（如果存在）
    if (n > 1) {
        dp[1] = max(dp[0] + scores[1], 0);
    }
    if (n > 2) {
        dp[2] = max(dp[1] + scores[2], 0);
    }

    // 从第4轮开始进行状态转移
    for (int i = 3; i < n; i++) {
        dp[i] = max(dp[i-1] + scores[i], dp[i-3]);
    }
    
    // 输出最终结果
    cout << dp[n-1] << endl;
    return 0;
}

python

def max_score(scores):
    n = len(scores)
    if n == 0:
        return 0
    
    dp = [0] * n
    
    # 初始化 dp[0]
    dp[0] = max(scores[0], 0)
    
    # 初始化 dp[1] 和 dp[2]（如果存在）
    if n > 1:
        dp[1] = max(dp[0] + scores[1], 0)
    if n > 2:
        dp[2] = max(dp[1] + scores[2], 0)
    
    # 从第4轮开始进行状态转移
    for i in range(3, n):
        dp[i] = max(dp[i-1] + scores[i], dp[i-3])
    
    return dp[-1]

# 输入处理
input_scores = list(map(int, input().strip().split(',')))
print(max_score(input_scores))

java

import java.util.*;

public class Main {
    public static int maxScore(int[] scores) {
        int n = scores.length;
        if (n == 0) return 0;
        
        int[] dp = new int[n];
        
        // 初始化 dp[0]
        dp[0] = Math.max(scores[0], 0);
        
        // 初始化 dp[1] 和 dp[2]（如果存在）
        if (n > 1) {
            dp[1] = Math.max(dp[0] + scores[1], 0);
        }
        if (n > 2) {
            dp[2] = Math.max(dp[1] + scores[2], 0);
        }
        
        // 从第4轮开始进行状态转移
        for (int i = 3; i < n; i++) {
            dp[i] = Math.max(dp[i-1] + scores[i], dp[i-3]);
        }
        
        return dp[n-1];
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] inputArray = input.split(",");
        int[] scores = new int[inputArray.length];
        
        // 转换输入为整数数组
        for (int i = 0; i < inputArray.length; i++) {
            scores[i] = Integer.parseInt(inputArray[i]);
        }
        
        // 输出结果
        System.out.println(maxScore(scores));
    }
}

题目描述

给定一个长度为 $n$ 的整型数组，表示一个选手在 $n$ 轮内可选择的牌面分数。

选手基于规则选牌，请计算所有轮结束后其可以获得的最高总分数。

选择规则如下：

在每轮里选手可以选择获取该轮牌面，则其总分数加上该轮牌面分数，为其新的总分数。

选手也可不选择本轮牌面直接跳到下一轮，此时将当前总分数还原为 $3$ 轮前的总分数，若当前轮次小于等于 $3$ （即在第 $1$、$2$、$3$ 轮选择跳过轮次），则总分数置为 $0$ 。

选手的初始总分数为 $0$ ，且必须依次参加每一轮。

输入描述

第一行为一个小写逗号分割的字符串，表示 $n$ 轮的牌面分数，$1<= n <=20$ 。

分数值为整数，$-100 <=$ 分数值 $<= 100$ 。

不考虑格式问题。

输出描述

所有轮结束后选手获得的最高总分数。

样例1

输入

1,-5,-6,4,3,6,-2

输出

11