fork(2) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool h[1000009]={0};
  4. int dp[1000009]={0};
  5. int a[1000009]={0};
  6. vector<int> v[1000009];
  7. int main()
  8. {
  9. int n,x,m=0,ans=0;
  10. scanf("%d",&n);
  11. for(int i=0;i<n;i++)
  12. {
  13. scanf("%d",&a[i]);
  14. h[a[i]]=1;
  15. m=max(a[i],m);
  16. }
  17. sort(a,a+n);
  18. for(int i=0;i<n;i++)
  19. {
  20. int p=0;
  21. if(h[a[i]])
  22. for(vector<int>::iterator it=v[a[i]].begin();it!=v[a[i]].end();it++)
  23. {
  24. p=max(p,dp[*it]);
  25. }
  26. dp[a[i]]=1+p;
  27. ans=max(ans,dp[a[i]]);
  28. for(int j=2;a[i]*j<=m;j++)
  29. {
  30. if(h[a[i]*j]==1)
  31. {
  32. v[a[i]*j].push_back(a[i]);
  33. }
  34. }
  35. }
  36. printf("%d\n",ans);
  37. return 0;
  38. }
Success #stdin #stdout 0.01s 23976KB
stdin
8
3 4 6 8 10 18 21 24
stdout
3