JOI2010 本戦 C - つらら

• 問題
• AC

つらら$v$より$v+1$のほうが長いとき、$v$は$v+1$が$L$に達して$0$に戻るまでは伸びない。この時$v+1$から$v$に辺を張ることにすると、DAGが得られる。そこで、トポロジカルソートした上で辺$(u, v)$に対して

$$\operatorname{dp}[v] \leftarrow \max(\operatorname{dp}[v], \operatorname{dp}[u] + L - a_v)$$

と更新していけば、最終的には$\operatorname{dp}[v] = v$が$0$に戻るまでの時間、となる。$\operatorname{dp}$の初期値は$\operatorname{dp}[v] := L - a_v$としておくのがわかりやすそう。${O}(N)$。