Codeforces Round #641 Div2.B Orac and Models 中文题解
Caro23333
2020-04-30 00:12:30
### Orac and Models 中文题解
考虑dp，不难设计出状态： $f_i$ 表示以编号为 $i$ 的模型结尾的最长合法序列长度。可以写出转移：
$$
f_i = \max\limits_{j\mid i, s_j<s_i} \{f_j + 1\}
$$
于是答案序列的长度为 $f_1,f_2,\cdots,f_n$ 中最大的一个。
复杂度分析：令 $s=\sum n$，如果你通过枚举因数来进行转移，将花费 $O(s\sqrt s)$的时间；如果通过枚举倍数来进行转移，那么根据调和级数的结论你将花费 $O(s\log s)$ 的时间。不过事实上两种方法均可通过此题。
Problem and Tutorial by Caro23333
```cpp
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 500005;
inline int readint()
{
int res = 0;
char c = 0;
while(!isdigit(c))
c = getchar();
while(isdigit(c))
res = res*10+c-'0', c = getchar();
return res;
}
int n,a[MAXN],f[MAXN];
int main()
{
int T = readint();
while(T--)
{
n = readint();
for(int i = 1; i<=n; i++)
a[i] = readint();
for(int i = 1; i<=n; i++)
f[i] = 1;
for(int i = 1; i<=n; i++)
for(int j = i*2; j<=n; j += i)
if(a[i]<a[j])
f[j] = max(f[j],f[i]+1);
int ans = 0;
for(int i = 1; i<=n; i++)
ans = max(ans,f[i]);
cout << ans << endl;
}
return 0;
}
```