drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ yukicoder 見積り大事 約数 数量が小さいことの活用：約数の個数 DP 数列 LIS 数学(整数問題) LIS の亜種だけど、雰囲気違って面白い！ 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。この部分列であって 狭義単調増加 後の index に出てくるやつは前の index にでてくるやつの倍数になっている という条件を満たすものの最長の長さを求めよ。 制約 考えたこと 単純に DP しよう。 dp[ v ] := 今見ている値が v のとき、v を最後の要素としたときの最長の長さ として、v の約数 d (< v) を全部見て chmax(dp[ v ], dp[ d ] + 1) とすればよい。v = 1 のときは dp[ v ] = 1 とする。計算量は となる。 #in… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F02%2F01%2F003300" title="yukicoder No.979 Longest Divisor Sequence - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-02-01 00:33:00 rich https://drken1215.hatenablog.com/entry/2020/02/01/003300 1.0 100%