节奏游戏的一首歌里依次出现 n 个音符。
第 i 个音符的分数是 a_i，可能是负数。
每个音符都要选择击打或放过。
如果紧挨着的前一个音符也击打了，这个音符就延续连击。
连击中第一个击打的音符得到分数的 1 倍，第二个得到 2 倍，第三个及之后击打的音符都得到 3 倍。
放过一个音符，连击就断了，之后击打的音符又成为连击的第一个（1 倍）。
第一个音符总是连击的第一个。
总分是击打的音符所得分数之和。
一个都不击打则为 0 分。
第一行给出 n，第二行给出用空格分开的 a_1 … a_n。
输出能得到的最大总分。
5 -1 5 3 -10 4
22
3 -5 -2 -7
0
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
即使是负分音符，击打它来延续连击，后面的音符就能得到 3 倍（5 5 -1 5 5 全部击打得 42 分，只放过 -1 得 30 分），所以只击打正分音符的贪心解是错的。
每经过一个音符，就延续“刚放过 / 连击第一个 / 第二个 / 第三个及以后”四个状态的最好分数，这样的动态规划 n 步就完成。
第一个陷阱是更新状态的顺序。
所有新值都必须用前一个音符的值来算，逐个立即覆盖的话，c2 会用到已经变了的 c1。
Python 用 skip, c1, c2, c3 = …，JS/TS 用数组解构 [skip, c1, c2, c3] = [...]，C# 用元组 (skip, c1, c2, c3) = (...) 可以一次性更新。
Java、C、Craykon 没有这种同时赋值，要先把新值算到临时变量里再搬过去。
C++ 可以用 std::tie(skip, c1, c2, c3) = std::make_tuple(...) 一次性更新，不过用临时变量更常见。
第二个陷阱是还到达不了的状态的初始值。
在第一个音符之前把 c1、c2、c3 设为 0，就等于第一个音符起就拿到了 2 倍、3 倍。
要从非常小的值开始，比如 Python float("-inf")、JS/TS -Infinity。
Java、C#、C、C++ 的整数没有无穷大，给 Integer.MIN_VALUE（int.MinValue、INT_MIN）加上负分会溢出：Java、C# 里变成很大的正数，C、C++ 里是未定义行为，所以用它的一半这样留有余地的值。
Craykon 没有这类常量，要自己写 -1 万亿这样的数。
第三，答案要在四个状态中取最大值，这样也包括放过最后一个音符和一个都不击打（0 分）的情况。
n = int(input())a = list(map(int, input().split())) # 노트 하나를 지날 때마다 상태 넷의 가장 좋은 점수를 이어 간다# skip: 이 노트를 보냈다(콤보 없음)# c1, c2: 이 노트가 콤보의 첫째·둘째# c3: 이 노트가 콤보의 셋째 이후(3배)NONE = float("-inf") # 아직 닿을 수 없는 상태skip, c1, c2, c3 = 0, NONE, NONE, NONEfor x in a: skip, c1, c2, c3 = max(skip, c1, c2, c3), skip + x, c1 + 2 * x, max(c2, c3) + 3 * xprint(max(skip, c1, c2, c3))const nums = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = nums[0];// skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배). -Infinity는 아직 닿을 수 없는 상태let skip = 0, c1 = -Infinity, c2 = -Infinity, c3 = -Infinity;for (let i = 1; i <= n; i++) { const x = nums[i]; [skip, c1, c2, c3] = [Math.max(skip, c1, c2, c3), skip + x, c1 + 2 * x, Math.max(c2, c3) + 3 * x];}console.log(Math.max(skip, c1, c2, c3));import { readFileSync } from "node:fs";const nums: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n: number = nums[0];// skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배). -Infinity는 아직 닿을 수 없는 상태let skip = 0, c1 = -Infinity, c2 = -Infinity, c3 = -Infinity;for (let i = 1; i <= n; i++) { const x: number = nums[i]; [skip, c1, c2, c3] = [Math.max(skip, c1, c2, c3), skip + x, c1 + 2 * x, Math.max(c2, c3) + 3 * x];}console.log(Math.max(skip, c1, c2, c3));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { // 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값 static final int NONE = Integer.MIN_VALUE / 2; public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); StringTokenizer st = new StringTokenizer(in.readLine()); // skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배) int skip = 0, c1 = NONE, c2 = NONE, c3 = NONE; for (int i = 0; i < n; i++) { int x = Integer.parseInt(st.nextToken()); int nSkip = Math.max(Math.max(skip, c1), Math.max(c2, c3)); int n1 = skip + x; int n2 = c1 + 2 * x; int n3 = Math.max(c2, c3) + 3 * x; skip = nSkip; c1 = n1; c2 = n2; c3 = n3; } System.out.println(Math.max(Math.max(skip, c1), Math.max(c2, c3))); }}using System;using System.Linq; class Program{ // 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값 const int None = int.MinValue / 2; static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); // skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배) int skip = 0, c1 = None, c2 = None, c3 = None; foreach (int x in a) { (skip, c1, c2, c3) = (Math.Max(Math.Max(skip, c1), Math.Max(c2, c3)), skip + x, c1 + 2 * x, Math.Max(c2, c3) + 3 * x); } Console.WriteLine(Math.Max(Math.Max(skip, c1), Math.Max(c2, c3))); }}#include <algorithm>#include <climits>#include <iostream> int main() { // 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값 const int NONE = INT_MIN / 2; int n; std::cin >> n; // skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배) int skip = 0, c1 = NONE, c2 = NONE, c3 = NONE; for (int i = 0; i < n; i++) { int x; std::cin >> x; int ns = std::max({skip, c1, c2, c3}); int n1 = skip + x, n2 = c1 + 2 * x, n3 = std::max(c2, c3) + 3 * x; skip = ns; c1 = n1; c2 = n2; c3 = n3; } std::cout << std::max({skip, c1, c2, c3}) << '\n';}#include <limits.h>#include <stdio.h> /* 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값 */#define NONE (INT_MIN / 2) static int max2(int a, int b) { return a > b ? a : b; } int main(void) { int n; scanf("%d", &n); /* skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배) */ int skip = 0, c1 = NONE, c2 = NONE, c3 = NONE; for (int i = 0; i < n; i++) { int x; scanf("%d", &x); int ns = max2(max2(skip, c1), max2(c2, c3)); int n1 = skip + x, n2 = c1 + 2 * x, n3 = max2(c2, c3) + 3 * x; skip = ns; c1 = n1; c2 = n2; c3 = n3; } printf("%d\n", max2(max2(skip, c1), max2(c2, c3))); return 0;}n = 控制台.读行().转数字();a = 控制台.读数字();// 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작은 값못감 = -1000000000000;// skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배)skip = 0;c1 = 못감;c2 = 못감;c3 = 못감;遍历 (x 在 a){ // 새 값은 모두 이전 값으로 계산한다: 먼저 따로 구해 두고 한꺼번에 바꾼다 새skip = 数学.较大值(数学.较大值(skip, c1), 数学.较大值(c2, c3)); 새c1 = skip + x; 새c2 = c1 + 2 * x; 새c3 = 数学.较大值(c2, c3) + 3 * x; skip = 새skip; c1 = 새c1; c2 = 새c2; c3 = 새c3;}控制台.输出(数学.较大值(数学.较大值(skip, c1), 数学.较大值(c2, c3)));