给定一个长度为 n 的严格单调递增的整数序列 a1,a2,…,an。
序列 a 的子序列可以表示为 ai1,ai2,…,aip，其中 1≤i1<i2<…<ip≤n。
我们希望找到一个 a 的子序列，使得该子序列满足：对于 j∈[1,p−1]，aij+1≤aij×2 恒成立。
我们认为，长度为 1 的子序列总是满足条件的。
请你计算并输出满足条件的子序列的最大可能长度。
问题 E: 最长子序列
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 7
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行包含一个整数 n。
第二行包含 n 个整数 a1,a2,…,an。
第二行包含 n 个整数 a1,a2,…,an。
输出描述
一个整数，表示满足条件的子序列的最大可能长度。
样例输入
10
1 2 5 6 7 10 21 23 24 49样例输出
4提示
前 5 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤2×105，1≤a1<a2<…<an≤109。
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版