問題一覧 > 通常問題

No.2218 Multiple LIS

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 150
作問者 : stoqstoq / テスター : ぷらぷら ShirotsumeShirotsume
5 ProblemId : 7703 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-18 08:26:50

問題文

長さ $N$ の整数列 $A = (A_1,\dots,A_N)$ が与えられます。
$A$ の連続とは限らない部分列 $(B_1,\dots,B_k)$ であって、 次の条件を満たすものの長さの最大値を求めてください。

  • 任意の $1 \leq i \leq k-1$ に対して、$B_{i+1}$ は $B_i$ の倍数である。
    長さ $1$ の部分列は条件を常に満たすことに注意。

入力

$N$
$A_1$ $\dots$ $A_N$

  • 入力は全て整数
  • $1 \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^5$

出力

条件を満たす部分列の長さの最大値を出力してください。

サンプル

サンプル1
入力
6
1 2 3 4 4 5
出力
4

例えば部分列 $(1,2,4,4)$ は条件を満たします。

条件を満たす部分列でこれより長いものは存在しないので、長さの最大値は $4$ です。

サンプル2
入力
1
1
出力
1

サンプル3
入力
10
3 2 9 1 9 7 18 8 36 1
出力
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。