yukicoder No.390 最長の数列

問題

No.390 最長の数列 - yukicoder

解法

DPをします.
dp[i] = x_iを最後の要素としたときのよい数列の最大の長さ
としておきます. 遷移は,
dp[i] = \max(dp[j] + 1, dp[i]) x_i は x_jの倍数
です. 右のdp[j]を固定して配るDPにすると,
計算量は O(\max{x_i}\log N)なります.
左を固定すると約数の列挙にO(\sqrt{\max{x_i}})かかるためO(N \sqrt{\max{x_i}})となり, ギリギリ間に合います.

提出

#279345 No.390 最長の数列 - yukicoder

感想

難しかったです.