yukicoder No.979 Longest Divisor Sequence

• 問題
• AC

一見して端からDPすれば良さそうに見える。つまり、$\operatorname{dp}[x] :=$位置$x$から始まる最長の部分列の長さ、として$\operatorname{dp}[N-1]=1$から逆順に埋めていく方法が考えらえるが、単純に$\operatorname{dp}[x] \leftarrow 1+\max \{\operatorname{dp}[y] : x|yかつx < yかつA_x < A_y\}$と遷移すると間に合わない。

約数の数があまり多くないことを利用すると遷移の数を減らせそう。つまり、$A_y (< A_x)$が$A_x$の約数であるような$y( $$\operatorname{dp}[y] \leftarrow \max (\operatorname{dp}[y], 1 + \operatorname{dp}[x])$$

と遷移したい。ただ、これでは同一の約数がたくさん存在するときに遷移先の候補が減っていない。同一の約数についてはいちばん右のものだけ見ればよいから、

$$\operatorname{stack}[k] := 数列(A_i)中に登場する整数kの位置を降順に保持したスタック$$

を最初に作っておいて、適当にポップしながらスタックの先頭にだけ遷移すればよい。