CFR 264 B. Good Sequences ( DP )

Problem - 264B - Codeforces
題意：
給一個非遞減數列，求一個序列的最長長度，序列滿足相鄰數值皆不互質。
解法：
首先因為輸入保證非遞減，我們可以直接無視序的存在，由數值小至大考慮，從而少一個維度的複雜度。一個數對求解過程中的貢獻是，可以更新比它大且與它有相同質因數的數。

int N;
vi A;

void init(){
    cin >> N;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    int all_one = 1;
    for( int i = 0; i < N; ++i )
        all_one &= A[ i ] == 1;
    if( all_one ){
        cout << 1 << endl;
        exit( 0 );
    }
}

vi np;
vvi pf; // prime factor table

vi acnt;
vi dp;

void preprocess(){
    np = vi( ( int ) 1e5 + 1 );
    pf = vvi( ( int ) 1e5 + 1 );
    for( int i = 2; i <= ( int ) 1e5; ++i )
        if( not np[ i ] )
            for( int j = i + i; j <= ( int ) 1e5; j += i )
                np[ j ] = 1,
                pf[ j ].emplace_back( i );
    acnt = dp = vi( ( int ) 1e5 + 1 );
    for( int i = 0; i < N; ++i )
        ++acnt[ A[ i ] ],
        dp[ A[ i ] ] = 1;
    for( int i = 2; i <= ( int ) 1e5; ++i )
        for( int j = 0; j < pf[ i ].size(); ++j )
            acnt[ pf[ i ][ j ] ] = 1; 
    for( int i = 2; i <= ( int ) 1e5; ++i ) if( acnt[ i ] ){
        for( int j = 0; j < pf[ i ].size(); ++j ) if( acnt[ pf[ i ][ j ] ] )
            upmax( dp[ i ], dp[ pf[ i ][ j ] ] + 1 );
        for( int j = 0; j < pf[ i ].size(); ++j ) if( acnt[ pf[ i ][ j ] ] )
            upmax( dp[ pf[ i ][ j ] ], dp[ i ] );
    }
}

void solve(){
    int ans = 0;
    for( int i = 2; i <= ( int ) 1e5; ++i )
        upmax( ans, dp[ i ] );
    cout << ans << endl;
}