ABC270D - Stones

考え方

「$\mathrm{dp}[n] = n$個から開始したときの答え（先手が取れる最大数）」とすると，（$A_{1} = 1$よりすべての石を取り尽くすことでゲームが終了するので）後手が取る石の個数は$n - \mathrm{dp}[n]$となる．

$n$個ある状態で，はじめに先手が$A_{i}$個とることを確定させると，「先手と後手が入れ替わった，初期値が$n - A_{i}$個の問題」に帰着する．この問題での青木君の答えは$\mathrm{dp}[n - A_{i}]$で，初期状態が$n - A_{i}$の高橋君の答えは$(n - A_{i}) - \mathrm{dp}[n - A_{i}]$となる．

つまり，dpの遷移は

\begin{aligned}
& \mathrm{dp}[n] \\
&= \max_{i} \Bigl\{A_{i} + \bigl[(n - A_{i}) - \mathrm{dp}[n - A_{i}]\bigr] \Bigr\}
\end{aligned}

となる．

回答例

N, K = map(int, input().split())
A = list(map(int, input().split()))

dp = [0] * (N + 1)
for n in range(1, N + 1):
    for a in A:
        if n - a < 0:break
        dp[n] = max(dp[n], n - dp[n - a])

print(dp[N])