0w1

CFR Educational 17 D. Maximum path ( DP )

Problem - D - Codeforces

題意:
有一個 3 * N 的矩陣,每個格子裡面有一個整數值。由左上角走到右下角,兩個格子可以互通若且唯若有公共邊,求路徑沒有重複格子的前提下,經過的格子值最大總和。

資料規模:
1 ≤ N ≤ 1e5
TL: 2000 ms
ML: 256 MB

解法:
dp[ i ][ j ]:準備從第幾行走出去,已考慮 j 列,此前提下最大總和
更新方法主要有三種,一種是直直走到下一列,另一種是走到下一列後向上或向下走,最後一種是走到下一列,向上 / 下走,接著拐一個ㄈ字形的彎回來。仔細想想,最後一種更新其實不難處理,每一次能把下一列三格都吃掉的時候丟進去更新一個最大值,這個值就是拐彎的最大值,因為前一次拐彎的到最大值的方法,加上當前這一列之後,仍然是個拐彎的方法。不用記錄所有之前拐彎的方法的原因是,若有記錄,則某個時機裡這記錄裡的所有值,在將來都一定會加上一樣的值 ( 列 ),才能以「拐彎的方法」苟存,所以當下更新的最大值一定最優。

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

注意:
動態規劃的時候要想清楚初始值,特別是要處理不可轉移的可能。第 23 行,不能為 0。

const int MAXN = 1e5;

int N;
int A[ 3 ][ MAXN ];
ll dp[ 3 ][ MAXN + 1 ];

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

void preprocess(){
  for( int i = 0; i < 3; ++i ){
    for( int j = 0; j <= N; ++j ){
      dp[ i ][ j ] = - ( 1LL << 50 );
    }
  }
  dp[ 0 ][ 0 ] = 0;
  ll S0 = - ( 1LL << 50 ), S2 = - ( 1LL << 50 );
  for( int i = 1; i <= N; ++i ){
    upmax( dp[ 1 ][ i ], dp[ 1 ][ i - 1 ] + A[ 1 ][ i - 1 ] );
    upmax( dp[ 1 ][ i ], dp[ 0 ][ i - 1 ] + A[ 0 ][ i - 1 ] + A[ 1 ][ i - 1 ] );
    upmax( dp[ 1 ][ i ], dp[ 2 ][ i - 1 ] + A[ 2 ][ i - 1 ] + A[ 1 ][ i - 1 ] );
    upmax( dp[ 0 ][ i ], dp[ 0 ][ i - 1 ] + A[ 0 ][ i - 1 ] );
    upmax( dp[ 0 ][ i ], dp[ 1 ][ i - 1 ] + A[ 1 ][ i - 1 ] + A[ 0 ][ i - 1 ] );
    upmax( dp[ 2 ][ i ], dp[ 2 ][ i - 1 ] + A[ 2 ][ i - 1 ] );
    upmax( dp[ 2 ][ i ], dp[ 1 ][ i - 1 ] + A[ 1 ][ i - 1 ] + A[ 2 ][ i - 1 ] );
    ll t = max( S0, S2 );
    upmax( S0, max( t, dp[ 0 ][ i - 1 ] ) );
    S0 += 1LL * A[ 0 ][ i - 1 ] + A[ 1 ][ i - 1 ] + A[ 2 ][ i - 1 ];
    upmax( S2, max( t, dp[ 2 ][ i - 1 ] ) );
    S2 += 1LL * A[ 2 ][ i - 1 ] + A[ 1 ][ i - 1 ] + A[ 0 ][ i - 1 ];
    upmax( dp[ 2 ][ i ], S0 );
    upmax( dp[ 0 ][ i ], S2 );
  }
}

void solve(){
  cout << dp[ 2 ][ N ] << endl;
}