EDPC C - Vacation

夏休み

考え方

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

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

$1$ 日目の場合。

よって最大値は $70$。

$2$ 日目の場合。

よって最大値は $120$。

$3$ 日目の場合。

よって最大値は $210$。

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

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

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

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

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

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

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

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

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

入力を受け取る。

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

各日について、そこまでの幸福度の最大値を求める。
その日に A・B・C のどれをしたかで、状態を分けて持つ。

$1$ 日目は、それぞれの行動をそのまま選ぶので次のようになる。

日	A で終わる	B で終わる	C で終わる
$1$ 日目	$10$	$40$	$70$

$2$ 日目に A をする場合、$1$ 日目は B または C である。
最大値は $\max(40,70)+20=90$ となる。

B をする場合は、A または C から遷移する。
最大値は $\max(10,70)+50=120$ となる。

C をする場合は、A または B から遷移する。
最大値は $\max(10,40)+80=120$ となる。

$2$ 日目まで求めると、次のようになる。

日	A で終わる	B で終わる	C で終わる
$1$ 日目	$10$	$40$	$70$
$2$ 日目	$90$	$120$	$120$

$3$ 日目も同様に計算する。

A で終わる場合を考える。
最大値は $\max(120,120)+30=150$ である。
B で終わる場合を考える。
最大値は $\max(90,120)+60=180$ である。
C で終わる場合を考える。
最大値は $\max(90,120)+90=210$ である。

最終的には次の状態になる。

日	A で終わる	B で終わる	C で終わる
$1$ 日目	$10$	$40$	$70$
$2$ 日目	$90$	$120$	$120$
$3$ 日目	$150$	$180$	$210$

最終日はどの行動で終わってもよいので、最大値 $210$ が答え。

特になし。

特になし。