Problem 3672 --2020-3-小 C 的数(number)-初中组

3672: 2020-3-小 C 的数(number)-初中组

"
Time Limit $2$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $6$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
小 C 非常喜欢数字。
这次,他得到了一个长度为 n 的正整数数列 A,第 i 项为 ai。
现在,小 C 想要找出来 A 中最长的子序列B = {b1, b2, · · · , bm},使得对于任意的二元组(i, j),bi 和 bj 满足倍数关系。
小 C 突然不会最长不下降子序列了,于是找到了你来帮他求出最长的子序列的长度。
子序列:对于长度为 n 的数列 A,对于 B = {b1, b2, · · · , bm},若 b1 = ap1 , b2 = ap2 , · · · , bm =apm,则必须要满足 1 ≤ p1 < p2 < · · · < pm ≤ n,这样的数列 B 称为 A 的子序列。其中子序列 B 可以为空。
倍数关:对于两个数 a, b,两者成倍数关系,即 a 能被 b 整除,或者 b 能被 a 整除,两者至少一种成立。
共两行,第一行有一个正整数 n,表示数列 A 的长度;
第二行有 n 个正整数,第 i 个数表示 ai。
仅一行一个数,表示子序列长度的最大值。
5
1 2 3 8 16
4
【样例 1 解释】
最长子序列为 {1, 2, 8, 16},长度为 4。
【数据范围】
测试点 N ai
1 =3 <=106
2 =8
3-4 <=20
5-6 <=5000
7-8 <=5*105
9-10 <=3*106 <=107
对于所有数据:0 < N ≤ 3 × 106,0 < ai ≤ 107
友情提示:输入数量很大,请使用scanf读入或者更好的输入方式,以及减少使用STL,以加快程序运行时间


推荐代码 查看3672 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$829 $ms] ldy6314 765207 2021-10-12 16:05:06
内存最少[$80208 $KB] ldy6314 765207 2021-10-12 16:05:06
第一AC ldy6314 765207 2021-10-12 16:05:06
第一挑战 ldy6314 765204 2021-10-12 14:18:40

赛题来源/所属竞赛 S:合肥市信息学 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛