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; }