CFR 429 B. Working out ( DP )

Problem - B - Codeforces
題意：
給一矩陣，格子上有權值。一個人由左上角向右或向下移動，至右下角。另一人由左下角向右或向上移動，至右上角。兩人會面恰好一次，該次權值不算，求兩人路徑權值總和。
解法：
預處理四個角分別到達某個格子能獲得的最大權值和。接著枚舉會面的格子搞一下就行了。

int N, M;
vvi A;

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

vvi dpq, dpp, dpz, dpm;

void preprocess(){
    dpq = dpp = dpz = dpm = vvi( N, vi( M + 1 ) );
    dpq[ 0 ][ 0 ] = A[ 0 ][ 0 ];
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < M; ++j ){
            if( i + 1 < N )
                upmax( dpq[ i + 1 ][ j ], dpq[ i ][ j ] + A[ i + 1 ][ j ] );
            if( j + 1 < M )
                upmax( dpq[ i ][ j + 1 ], dpq[ i ][ j ] + A[ i ][ j + 1 ] );
        }
    dpp[ 0 ][ M - 1 ] = A[ 0 ][ M - 1 ];
    for( int i = 0; i < N; ++i )
        for( int j = M - 1; j >= 0; --j ){
            if( i + 1 < N )
                upmax( dpp[ i + 1 ][ j ], dpp[ i ][ j ] + A[ i + 1 ][ j ] );
            if( j - 1 >= 0 )
                upmax( dpp[ i ][ j - 1 ], dpp[ i ][ j ] + A[ i ][ j - 1 ] );
        }
    dpz[ N - 1 ][ 0 ] = A[ N - 1 ][ 0 ];
    for( int i = N - 1; i >= 0; --i )
        for( int j = 0; j < M; ++j ){
            if( i - 1 >= 0 )
                upmax( dpz[ i - 1 ][ j ], dpz[ i ][ j ] + A[ i - 1 ][ j ] );
            if( j + 1 < M )
                upmax( dpz[ i ][ j + 1 ], dpz[ i ][ j ] + A[ i ][ j + 1 ] );
        }
    dpm[ N - 1 ][ M - 1 ] = A[ N - 1 ][ M - 1 ];
    for( int i = N - 1; i >= 0; --i )
        for( int j = M - 1; j >= 0; --j ){
            if( i - 1 >= 0 )
                upmax( dpm[ i - 1 ][ j ], dpm[ i ][ j ] + A[ i - 1 ][ j ] );
            if( j - 1 >= 0 )
                upmax( dpm[ i ][ j - 1 ], dpm[ i ][ j ] + A[ i ][ j - 1 ] );
        }
}

void solve(){
    int ans = 0;
    for( int i = 1; i + 1 < N; ++i )
        for( int j = 1; j + 1 < M; ++j )
            upmax( ans, dpq[ i - 1 ][ j ] + dpp[ i ][ j + 1 ] + dpz[ i ][ j - 1 ] + dpm[ i + 1 ][ j ] ),
            upmax( ans, dpq[ i ][ j - 1 ] + dpp[ i - 1 ][ j ] + dpz[ i + 1 ][ j ] + dpm[ i ][ j + 1 ] );
    cout << ans << endl;
}