思路参考:https://blog.nowcoder.net/n/7937ea0fe884441994a04e9f91cd9a8f
先对数组排序,问题变成寻找满足条件的最长子序列,很容易联想到dp。于是有了一个基础的动态转移方程:
其中表示以第
个数为最后一个元素构造的序列中最大的序列长度。
这是一个的算法,只能得80分。
为了优化,可以从质因数分解的角度考虑。设为因式包含
的最大序列长度,换句话说,如果有一个合法的序列中其中一个元素包含了因子
,那
就可以将这个序列纳入考虑范围。以如下数据为例:
2 3 4 6 9
其中的一个合法的序列为:
2 4 6 9
2包含2,4包含2,6包含2和3,9包含3,因此整个序列包含了{2,3},因此和
就至少为4(当然这就是最后答案)。
我们需要在循环元素的过程中不断更新数组的值。例如,当遇到6时,6包含因数2和3,我们观察到先前
的值为2,
的值为1,现在我们可以把6接在包含2和3因子的序列后面,因此
、
都要更新为
,也就是3。
按照这种思路,整体算法就是:
- 排序;
- 循环元素:
(1) 寻找当前元素的所有因子,找出其中最大的
值
;
(2) 将当前元素所有的因子i对应的更新为
;
- 找出最大的
。
一个细节是,我们仅需要枚举质因子就足够了,不过本题考虑到因子层面也就可以通过了,整体的时间复杂度为。
代码如下:
#include <bits/stdc++.h> #define MAXN 110000 using namespace std; int a[MAXN], dp[MAXN], T, n; int main(){ scanf("%d",&T); while(T--){ int res = 0; scanf("%d", &n); memset(dp, 0, sizeof(dp)); for(int i=0;i<n;i++) scanf("%d", &a[i]); sort(a, a+n); for(int i=0;i<n;i++){ int tmpmax = 0, left = a[i]; for(int j=2;j*j<=a[i];j++){ if(a[i] % j != 0) continue; if(dp[j] > tmpmax) tmpmax = dp[j]; while(left % j == 0) left = left / j; } if(left != 1 && dp[left] > tmpmax) tmpmax = dp[left]; for(int j=2;j*j<=a[i];j++) if(a[i] % j == 0) dp[j] = tmpmax + 1; if(left != 1) dp[left] = tmpmax + 1; if(tmpmax + 1 > res) res = tmpmax + 1; } printf("%d\n", res); } return 0; }