注意卡常

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;

int n, a[N], dp[N];
vector<int> b[N], fa[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int x = 1; x <= a[i] / x; x++) {
            if (a[i] % x == 0) {
                b[i].push_back(x);
                if (x != 1) fa[x].push_back(i);
                if (a[i] / x != x) {
                    b[i].push_back(a[i] / x);
                    if (a[i] / x != 1) fa[a[i] / x].push_back(i);
                }
            }
        }
    }

    for (int i = 1; i <= 100000; i++) {
        sort(fa[i].begin(), fa[i].end());
    }

    for (int i = 1; i <= n; i++) dp[i] = 1;

    for (int i = 1; i <= n; i++) {
        for (int x: b[i]) {
            if (x == 1) continue;
            int l = 0, r = int(fa[x].size()) - 1, pos = -1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (a[fa[x][mid]] >= a[i]) r = mid - 1, pos = mid;
                else l = mid + 1;
            }
            if (pos != -1 && pos != 0) {
                pos--;
                //cout << (*pos) << " " << a[i] << "\n";
                dp[i] = max(dp[i], dp[fa[x][pos]] + 1);
            }
        }
    }
    //for (int i = 1; i <= n; i++) cout << dp[i] << " "; cout << "\n";


    int ans = *max_element(dp + 1, dp + n + 1);
    cout << ans << "\n";


    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla