Editorial for Bedao Grand Contest 06 - LDS


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Code mẫu

#include <bits/stdc++.h>

using namespace std;
const string filename = "LDS";

int n;
int a[1000001], pos[1000001];
int f[1000001];

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen( (filename + ".inp").c_str(), "r", stdin);
    freopen( (filename + ".out").c_str(), "w", stdout);

    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
        pos[a[i]] = i;
    }
    int res = 0;
    for (int i=1;i<=n;i++)
        f[i] = 1;
    for (int i=1;i<=n;i++)
    {
        res = max(res, f[a[i]]);
        for (int j=a[i];j<=n;j+=a[i])
            if (pos[j] > i)
                f[j] = max(f[j], f[a[i]] + 1);      
    }
    cout << res;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.