【競プロ】ABC369　D問

動的計画法 (DP) を勉強しています。
ABC369 の D問 が、動的計画法の入門に良さそうなので、自分 (初心者) が考えたことを共有します。

【問題の要点】
・与えられたモンスターを順番に、倒す/倒さないを選択する。
・モンスターを倒したとき、奇数匹目なら「経験値」を得られ、偶数匹目なら「経験値 x 2」を得られる。
・最後までで得られる経験値の最大値を出力する。
・経験値が多いモンスターは、おそらく偶数匹目に倒したい。
　　(これが直前のモンスターを「倒さない」選択をする理由と思います)
・2匹連続で「倒さない」選択は、有り得ない。
　　(「2匹連続で倒す」と「2匹連続で倒さない」は、次のモンスターの偶奇が同じなので、「倒す」選択の方が経験値が必ず多い)

入力例1

5
1 5 3 2 7

について考えます。

結論から言ってしまいますが、最後に作りたい表は、

となります。

【表の埋め方】
・例えば、「4匹目に出会うモンスターを倒すのが偶数回目」だった場合、
　「2匹目に出会うモンスターを倒すのが奇数回目」だった場合 + 4匹目の経験値 x 2
　と
　「3匹目に出会うモンスターを倒すのが奇数回目」だった場合 + 4匹目の経験値 x 2
　の、どちらか大きい方、となります。
　(2匹目が奇数回目 → 4匹目が偶数回目　ということは、「3匹目を倒さない」選択をしたということです)
・同様に例えば、「4匹目に出会うモンスターを倒すのが奇数回目」だった場合、
　「2匹目に出会うモンスターを倒すのが偶数回目」だった場合 + 4匹目の経験値
　と
　「3匹目に出会うモンスターを倒すのが偶数回目」だった場合 + 4匹目の経験値
　の、どちらか大きい方、となります。
　(2匹目が偶数回目 → 4匹目が奇数回目　ということは、「3匹目を倒さない」選択をしたということです)
・そして、「1匹目に出会うモンスター」について考えます。
　「1匹目に出会うモンスターを倒すとき」は必ず奇数回目です。
　なので、(計算しやすくすために便宜上、-1 と 0 を使います)
　「-1匹目に出会うモンスターを倒すのが偶数回目」だった場合 + 1匹目の経験値
　と
　「0匹目に出会うモンスターを倒すのが偶数回目」だった場合 + 1匹目の経験値
　の、どちらか大きい方、となります。
・「1匹目に出会うモンスターを偶数回目に倒す」ということはあり得ません。
　なので、
　「-1匹目に出会うモンスターを倒すのが奇数回目」だった場合 + 1匹目の経験値 x 2
　と
　「0匹目に出会うモンスターを倒すのが奇数回目」だった場合 + 1匹目の経験値 x 2
　の、どちらか大きい方、となりますが、
　あり得ないので、「ものすごく少ない数 (例えば -10000000000)」を当てはめておくことで、その後の計算の過程で、自然と、選択の対象から外れていくことになります。
　(どうして、「ものすごく少ない数」を-10000000000 に設定するか、というと、問題の制約で「モンスターの経験値」が 1000000000 までは登場する可能性があるからです)

【計算の前段階】
最初に以下の表 (2 x 7 の配列) を作っておきます。

【計算して、表を埋めていきます】
・出会うモンスター 1匹目の「倒すのが奇数回目」
　「0 + 1」と「0 + 1」の大きい方　→　1
・出会うモンスター 1匹目の「倒すのが偶数回目」
　「-10000000000 + 1 x 2」と「-10000000000 + 1 x 2」の大きい方　→　-9999999998
・出会うモンスター 2匹目の「倒すのが奇数回目」
　「0 + 5」と「-9999999998 + 5」の大きい方　→　5
・出会うモンスター 3匹目の「倒すのが偶数回目」
　「-10000000000 + 5 x 2」と「1 + 5 x 2」の大きい方　→　11
(以下、同様に 3匹目、4匹目・・と計算していきます)

【最後に】
答えは、
「出会う最後のモンスターを倒すのが奇数回目」と
「出会う最後のモンスターを倒すのが偶数回目」の、どちらか大きい方、となります。

私のコードはここをご参照ください。 (言語はPythonです)
解説は以上です。