EDPC C - Vacation

考え方

$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)+90=210$

と出せる。
これならDPを $1$ つ進めるときに比較 $3$ 回と加算 $3$ 回だけで済むので、計算量は $O(N)$。
$N$ が $10$ 万でも余裕で間に合う。
DPスタート部分は、$1$ 日目だけデータをそのまま入れる。
あるいは、$0$ 日目時点で幸福度 $0$ と初期化してもよい。

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

もし実際の経路まで要求された場合は、DP表のバックトレースで普通に解ける。
つまり、以下の手順で求められる。

• $3$ 日目に最大値を記録したのはC
• $2$ 日目にC以外で最大値を記録したのはB
• $1$ 日目にB以外で最大値を記録したのはC

ただし、これをやるために、全日分のDP表か、どこから遷移したかの情報を保存しておく必要はある。

入力例1での動作

入力を受け取る。

n: 3
a: {10, 20, 30}
b: {40, 50, 60}
c: {70, 80, 90}

dp の中身は以下とする。

• dp[0] は「その日に A をする場合の幸福度最大値」
• dp[1] は「その日に B をする場合の幸福度最大値」
• dp[2] は「その日に C をする場合の幸福度最大値」

初日分で dp を初期化する。

dp: {10, 40, 70}

$2$ 日目の分を更新する。

$2$ 日目に A をする場合、$1$ 日目は B または C。
よって、max(dp[1], dp[2])+a[1] $= \max(40,70)+20 = 90$。
$2$ 日目に B をする場合、$1$ 日目は A または C。
よって、max(dp[0], dp[2])+b[1] $= \max(10,70)+50 = 120$。
$2$ 日目に C をする場合、$1$ 日目は A または B。
よって、max(dp[0], dp[1])+c[1] $= \max(10,40)+80 = 120$。

dp: {90, 120, 120}

$3$ 日目の分を更新する。

$3$ 日目に A をする場合、$2$ 日目は B または C。
よって、max(dp[1], dp[2])+a[2] $= \max(120,120)+30 = 150$。
$3$ 日目に B をする場合、$2$ 日目は A または C。
よって、max(dp[0], dp[2])+b[2] $= \max(90,120)+60 = 180$。
$3$ 日目に C をする場合、$2$ 日目は A または B。
よって、max(dp[0], dp[1])+c[2] $= \max(90,120)+90 = 210$。

dp: {150, 180, 210}

最終日には何をやってもいいので、dp の最大値 $210$ が答え。

注意点

特になし。

別解

特になし。