CFR Educational 17 D. Maximum path ( DP )
題意:
有一個 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; }