[Daimayuan] 优美！最长上升子序列（C++，DP）

多组数据。

每组将给定一个数组。派派希望从中选择一个递增的子序列，越长越好。

但派派认为，这样选出来的子序列依然不够「优美」，形式化的讲，派派希望选择的下标（从 $1$ 开始）需要满足

i1∣i2∣i3∣⋯∣iki_1∣i_2∣i_3∣⋯∣i_ki1​∣i2​∣i3​∣⋯∣ik​

其中 $a|b$ 表示整除， 即 $a$ 是 $b$ 的约数。

请你帮助派派完成任务吧！

注：子序列的含义不再赘述。

输入格式

第一行一个整数 $T$，表示接下来有 $T$ 组数据。

每组数据包含两行，第一行包含一个整数 $N$。

随后一行，包含 $N$ 个整数，表示原数组 {A}\\{A\\}{A}。

输出格式

对于每组数据，输出一行，包含一个数，表示能选出的「优美」的最长上升子序列长度。

数据规模

• $1\le T\le 100$
• 1≤N≤1061≤N≤10^61≤N≤106,但保证 ∑i=1TNi≤106\\sum_{i=1}^{T}{N_i≤10^6}∑i=1T​Ni​≤106
• 1≤Ai≤1091≤A_i≤10^91≤Ai​≤109

样例输入

4
4
1 4 6 7
2
2 2
10
1 2 3 4 5 6 7 8 9 10
10
10 9 8 6 5 2 3 1 2 1

样例输出

3
1
4
1

解释：

对于第一组数据，能选择的「优美」最长上升子序列为 {A1,A2,A4}={1,4,7}\\{A_1,A_2,A_4\\}=\\{1,4,7\\}{A1​,A2​,A4​}={1,4,7}。

对于第三组数组，选择 {A1,A2,A4,A8}={1,2,4,8}\\{A_1,A_2,A_4,A_8\\}=\\{1,2,4,8\\}{A1​,A2​,A4​,A8​}={1,2,4,8}。

对于第四组数据，可选择的「优美」最长上升子序列长度为 $1$。

解题思路

在寻找「优美」的最长上升子序列之前，我们先回顾一下最长上升子序列的寻找

for (int i = 1; i <= n; i++) {for (int j = 1; j < i; j++) {if (num[i] > num[j]) {pre[i] = max(pre[i], pre[j] + 1);}}
}

pre[i]中存储的是以对应num[i]结尾的最长上升子序列长度

要想寻找以num[i]结尾的最长上升子序列，我们只需要找到num[i]所能接上的最长前缀pre[j]($1\le j<i$)即可

如果想采用同样的思路，我们会遇到一个问题

因为题目要求索引可以逐个整除，但是我们很难找到所有符合要求的索引

虽然向前找很难，但是向后找很容易，例如，对于$i$，符合条件的索引即为$k\ast i(k\in Z)$

所以我们更新一下算法

for (int i = 1; i <= n; i++) {for (int j = 2 * i; j <= n; j += i) {if (num[i] < num[j]) {pre[j] = max(pre[j], pre[i] + 1);}}
}

与常规动态规划的更新方式不同，我们不是根据过去的结果推导出当前的值，而是根据当前的结果去推导未来的值

这种方法可行的原理是：在到达pre[i]之前，我们已经尝试用所有符合条件的pre[j]($1\le j<i$)去更新pre[i]了，从结果来看，这与之前是一致的

然后计算一下时间复杂度O(Nlog2N)O(Nlog_2N)O(Nlog2​N)，可以接受

最后，AC代码如下

#include <iostream>
using namespace std;
const int max_t = 100;
const int max_n = 1e6;
const int max_a = 1e9;int t, n, arr[max_n + 1];
int dp[max_n + 1];int main() {cin >> t;for (int i = 0; i < t; i++) {cin >> n;for (int j = 1; j <= n; j++) {cin >> arr[j];}int ans = 1;for (int j = 1; j <= n; j++) dp[j] = 1;for (int j = 1; j <= n; j++) {int z;for (z = 2 * j; z <= n; z += j) {if (arr[z] > arr[j]) {dp[z] = max(dp[z], dp[j] + 1);ans = max(ans, dp[z]);}}}cout << ans << endl;}return 0;
}