CFR 255 C. Almost Arithmetical Progression ( Binary Search + DP )

Problem - 255C - Codeforces

題意：
給一個序列。求一個最長子序列的長度，子序列滿足相鄰的數字的差是正負交替。ex: 10, 20, 10, 20

數據範圍：
序列長度 1 ≤ N ≤ 4000
元素大小 1 ≤ B[ i ] ≤ 1e6

解法：
對每個元素預處理出現在哪些位置。接著考慮動態規劃
dp[ i ][ j ] : 以 i 為下標的元素為倒數第二元素，以 j 為下標的元素為最後一個元素，此時的最長合法子序列長度
根據定義，子序列下一個元素必須是 B[ i ]，因此利用預處理的位置表，做 upper_bound 進行 O( lg N ) 查詢大於 j 且值為 B[ i ] 的最小下標， O( 1 ) 更新。

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

int N;
vi B;

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

map< int, vi > v_pos;
vvi dp;

void preprocess(){
    for( int i = 0; i < N; ++i )
        v_pos[ B[ i ] ].emplace_back( i );
    dp = vvi( N, vi( N, 2 ) );
    for( int i = 0; i < N; ++i )
        dp[ i ][ i ] = 1;
    for( int i = 0; i < N; ++i )
        for( int j = i + 1; j < N; ++j ){
            auto it = upper_bound( v_pos[ B[ i ] ].begin(), v_pos[ B[ i ] ].end(), j );
            if( it != v_pos[ B[ i ] ].end() )
                upmax( dp[ j ][ *it ], dp[ i ][ j ] + 1 );
        }
}

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