リズムゲームの一曲に、ノーツが 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 点）、0 より大きいノーツだけ叩く欲張り解は間違いです。
ノーツを一つ過ぎるたびに「今見送った・コンボ一番目・二番目・三番目以降」の四つの状態のいちばん良い点数を引き継ぐ動的計画法なら 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)));