CFR 566 F. Clique in the Divisibility Graph ( DP, Math, Complexity Analysis )

Problem - 566F - Codeforces

題意：
給一個嚴格遞增序列。求子序列最長長度，子序列滿足所有相鄰元素對，後一個元素可以被前一個整除。

資料規模：
序列長度 1 ≤ N ≤ 1e6
元素大小 1 ≤ A[ i ] ≤ 1e6
時限 1000 ms
記憶體 256 MB

解法：
注意到 [ 1, N ] 的數的因數個數總和約為 SIGMA{ 1 / i | 1 ≤ i ≤ N } = N lg N。因此可以直接開一個 dp 表，每一次對該元素的所有倍數更新。
dp[ i ] : 以 i 結尾的數，合法序列目前最長長度可以是多少

時間 / 空間複雜度：
O( N lg N )

閒話：
以前都一直聽動態規劃的時間複雜度就是狀態數 * 轉移維度。但最近才慢慢領悟，原來其實是 max{ 最大可能的須拜訪的狀態數, 最大可能的總轉移次數 }。

int N;
vi A;

void init(){
    cin >> N;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

int maxa;
vi dp;

void preprocess(){
    maxa = *max_element( A.begin(), A.end() );
    dp = vi( maxa + 1, 1 );
    for( int i = 0; i < N; ++i )
        for( int j = A[ i ] + A[ i ]; j <= maxa; j += A[ i ] )
            upmax( dp[ j ], dp[ A[ i ] ] + 1 );
}

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