DPまとめコンテスト/C - Vacation - 競技プログラミング用 知識集積所【7/10更新】

---

問題

DP-C

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法

考え方

N（最大10万）回の選択があり、初日は3択、残りの日は2択。
愚直に全ルート試すのは明らかに無理。

ということで、まずは愚直解を十分書き出せる例で様子を見て、計算を省けそうなところを探す。
入力例1で各日時点での最大幸福度を求めてみよう。

1日目の場合。

• Aをするなら幸福度は10
• Bをするなら幸福度は40
• Cをするなら幸福度は70

よって最大値は70。

2日目の場合。

• ABをするなら幸福度は10+50=60
• ACをするなら幸福度は10+80=90
• BAをするなら幸福度は40+20=60
• BCをするなら幸福度は40+80=120
• CAをするなら幸福度は70+20=90
• CBをするなら幸福度は70+50=120

よって最大値は120。

3日目の場合。

• ABAをするなら幸福度は10+50+30=90
• ABCをするなら幸福度は10+50+90=150
• ACAをするなら幸福度は10+80+30=120
• ACBをするなら幸福度は10+80+60=150
• BABをするなら幸福度は40+20+60=120
• BACをするなら幸福度は40+20+90=150
• BCAをするなら幸福度は40+80+30=150
• BCBをするなら幸福度は40+80+60=180
• CABをするなら幸福度は70+20+60=150
• CACをするなら幸福度は70+20+90=180
• CBAをするなら幸福度は70+50+30=150
• CBCをするなら幸福度は70+50+90=210

よって最大値は210。

さて、3日目の詳細を見て、2日目の計算を流用できる部分を探す。

• ABAをするなら幸福度は10+50+30=90
• ACAをするなら幸福度は10+80+30=120
• BCAをするなら幸福度は40+80+30=150
• CBAをするなら幸福度は70+50+30=150

Aで終わるこれら4つは、実は2日目のうち最後にBかCをやる

• ABをするなら幸福度は10+50=60
• ACをするなら幸福度は10+80=90
• BCをするなら幸福度は40+80=120
• CBをするなら幸福度は70+50=120

のうしろに+30をつけただけである。
Bで終わる4つ、Cで終わる4つも同様。

ということは、これらは実は2日目時点で

• Aで終わる場合の最大値は90
• Bで終わる場合の最大値は120
• Cで終わる場合の最大値は120

を出しておけば、3日目は

• Aで終わる場合の最大値はmax(120,120)+30=150
• Bで終わる場合の最大値はmax(90,120)+60=180
• Cで終わる場合の最大値はmax(90,120)+120=180
• 3日目の最大値は180（参考のために書いたが、この数値を継承する必要がないので最後1日以外は端折ってよい）

と出せる。
これならDPを1つ進めるときに比較3回と加算3回だけで済むので、Nが10万でも余裕で間に合う。

DPスタート部分は、1日目だけデータをそのまま入れてもいいし、0日目時点で幸福度0と初期化してもよい。

考えることは多いが、実装はDPコンテストの中で一番簡単。

解答例

解答例

注意点

別解