ABC188 E Peddler
制約より必ずDAGとなることを利用する.
メモ化再帰をDFSを用いて行っていく.
$ dp_v
:= 街
$ v
から到達できる街における金の最高値 とする.
ある頂点
$ v
の
$ dp_v
の値を計算することを考える.
$ dp_v = max(dp_v, dp_c)
,
$ dp_v = max(dp_v, A_v)
とすることで更新できる.
$ dp_v
の値が分かれば,
$ dp_v - A_v
の最大値が答えとなる.
計算量は
$ O(N)
である.
実装例:
https://atcoder.jp/contests/abc188/submissions/19346585