CFR 358 D. Dima and Hares ( DP )

Problem - D - Codeforces

題意：
給一排兔子，用三階段的獲益描述。每個兔子都要恰選一次，而各自得到的獲益為其第 ( 左邊已被選 + 右邊已被選 ) + 1 階段的獲益。求最大可能總獲益。

資料規模：
1 ≤ n ≤ 3000
0 ≤ ai, bi, ci ≤ 1e5
時限 2000 ms
記憶體 256 MB

解法：
本來想的是 2 * N * N * 2 的狀態數解法，但仔細想想，可以只有 2 * N，轉移 O( 1 )
dp[ i ][ j ] : j - 1 已取，[ j, N ) 的子問題解
dp[ i ][ j ] = max( W[ i ][ j ] + dp[ 1 ][ j + 1 ], W[ i + 1 ][ j ] + dp[ 0 ][ j + 1 ] )
也就是，對於每個已固定左邊是否已取的元素，我們只需考慮究竟是它還是右邊的元素先被取。

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

int N;
vvi W;

void init(){
    cin >> N;
    W = vvi( 3, vi( N ) );
    for( int i = 0; i < 3; ++i )
        for( int j = 0; j < N; ++j )
            cin >> W[ i ][ j ];
}

int dp[ 2 ][ 3000 + 1 ];

void preprocess(){
    memset( dp, -1, sizeof( dp ) );
}

int dfs( int a, int n ){
    if( n + 1 == N )
        return W[ a ][ n ];
    int &res = dp[ a ][ n ];
    if( ~res )
        return res;
    upmax( res, W[ a ][ n ] + dfs( 1, n + 1 ) );
    upmax( res, W[ a + 1 ][ n ] + dfs( 0, n + 1 ) );
    return res;
}

void solve(){
    cout << dfs( 0, 0 ) << endl;
}