Open1

ABC369D - Bonus EXP復習

junjun

問題文

モンスターが N 匹
A_i :i 匹目のモンスターの強さ
各モンスターに対して、「逃がす」か「倒す」かを選ぶことができる
得られる経験値

  • 逃がす:0
  • 強さが Xのモンスターを倒した：X（偶数回目は2X）
    ans:合計としてありえる経験値の最大値

入力形式

N
A_1, A_2, \dots, A_N

偶数回目の行動と奇数回目の行動を別々に管理し、それぞれの行動で得られる最大の経験値を計算するといけるらしい　
dpeven と dpodd の2つの配列を使って、偶数回目と奇数回目の行動で得られる最大経験値を管理
dpeven[i] :i匹目のモンスターまでの間に偶数回倒したときの最大経験値
dpodd[i] :i匹目のモンスターまでの間に奇数回倒したときの最大経験値

def max_experience(N, A):
    dpeven = [0] * (N + 1)
    dpodd = [-float('inf')] * (N + 1)

    for i in range(1, N + 1):
        dpeven[i] = max(dpeven[i-1], dpodd[i-1] + 2 * A[i-1])
        dpodd[i] = max(dpodd[i-1], dpeven[i-1] + A[i-1])

    return max(dpeven[N], dpodd[N])

# 入力の読み込み
N = int(input())
A = list(map(int, input().split()))

# 結果の出力
print(max_experience(N, A))

フロー

  1. 初期化:

    • dpeven[0] = 0: モンスターを倒さない場合の経験値です。
    • dpodd[0] = -∞: 奇数回目の行動がないため、無効

  2. 状態遷移:

    • dpeven[i] は、dpeven[i-1] と dpodd[i-1] + 2 * A[i-1] の最大値を取る
    • dpodd[i] は、dpodd[i-1] と dpeven[i-1] + A[i-1] の最大値を取る

  3. 結果:

    • dpeven[N] と dpodd[N] の最大値が答え

計算量
このアルゴリズムは、モンスターの数に対して線形時間（O(N)）