問題

考察

料理店から生きて退店する条件の下、食べた料理の美味しさの総和として考えられる最大値を求めてください問題です。

高橋くんは最初、お腹を壊していない
高橋くんは最初、食べた料理の美味しさの総和は$0$(何も食べてないため)

以上の2点を出発点として動的計画法で解くことができないか考えていきます。
そのために下記の動的計画法用の変数$dp_{i,j}$を用意してみます。

$dp_{i, j}$: 高橋くんに、$i$番目の料理まで提供が終わった。そして高橋くんの現在のお腹の状態が$j$である。この状況下で考えられる美味しさの総和の最大値。($j=0$:お腹を壊していない。$j=1$:お腹を壊している。)

もし、上記の変数$dp_{i,j}$を正しく求めることができたなら、最終的な答えは「$dp_{N, 0}$」と「$dp_{N, 1}$」のうちのより大きい方になります。
では出発点から変数$dp_{i,j}$の中身を順番に求める方法を考えます。

まずの出発点についてですが、上記の通り「最初、お腹を壊していない」「最初、食べた料理の美味しさの総和は$0$」です。つまり出発点は、
$$dp_{0, 0} = 0$$
であるといえます。

次に、1番目料理から$dp_{i, j}$を順に求める方法を考えていきます。そのために、$dp_{i-1, 0}$と$dp_{i-1, 1}$の値が既知でならば$dp_{i, 0}$と$dp_{i, 1}$を求めることができるか考えてみます。
高橋くんは提供された料理を「食べる」「下げてもらう」という選択肢があります。それぞれの場合を考えていきましょう。

食べる場合

$i$番目の料理が「解毒剤入り」か「毒入り」かで分けて考えていきます。

料理が「解毒剤入り」だった場合、お腹を壊していなければお腹を壊していないまま。お腹を壊していればお腹を壊していない状態になります。つまり、下記のことがいえます。

「$dp_{i, 0}$」が以下の値になる可能性がある。
- $dp_{i-1, 0} + Y_i$(お腹を壊していない状態で料理を食べたケース)
- $dp_{i-1, 1} + Y_i$(お腹を壊している状態で料理を食べたケース)

次に、料理が「毒入り」だった場合、お腹を壊していなければお腹を壊す。お腹を壊していると死んでしまいます。生きて退店することが条件のため、お腹を壊している状態では「食べる」という選択はそもそもできません。そのため、お腹を壊していない状態で食べたときのみを考えればいいです。つまり下記のことがいえます。

「$dp_{i, 1}$」が以下の値になる可能性がある。
- $dp_{i-1, 0} + Y_i$(お腹を壊していない状態で料理を食べたケース)

下げてもらう場合

料理を下げてもらう場合は、お腹の状態も美味しさの総和にも変化はありません。つまり、下記のことがいえます。

「$dp_{i, 0}$」が以下の値になる可能性がある。
- $dp_{i-1, 0}$(お腹を壊していない状態を維持)
「$dp_{i, 1}$」が以下の値になる可能性がある。
- $dp_{i-1, 1}$(お腹を壊している状態を維持)

以上のことから、$dp_{i, 0}$と$dp_{i, 1}$について、可能性がある値の中から最大のものに更新をすることで、$dp_{i, 0}$と$dp_{i, 1}$を求めることができます。

このことから、出発点である$dp_{0, 0} = 0$から順番に計算することで、「$dp_{N, 0}$」と「$dp_{N, 1}$」まで求めることができます。

これで、計算量$O(N)$と十分に間に合う時間で求めることができます。

提出コード(コンテスト後)

ご不明点などがあれば教えていただけると幸いです。