TIOJ 1908 大根蘿蔔 ( DP, bitmask )
1908 - 大根蘿蔔 | TIOJ INFOR Online Judge
Problem Description:
You are given a matrix of N * N, each cell with a positive value. You can take values away from each cell at most once, in any order, but after taking a value from a particular cell, all values in the cells within the 3 * 3 matrix with it as centre would be changed to 0. What is the maximum possible sum of values that can be taken?
Constraints:
1 ≤ N ≤ 22
1 ≤ val[ i ][ j ] ≤ 1e6
TL: 4000 ms
ML: 128 MB
Solution:
Let's come up with a simple dp solution:
dp[ i ][ j ] : having considered top i rows, and the last row considered has state of being taken described as j, the maximal possible sum
Since 22 * 2^22 will cause overflow in memory, we would use the rolling dp technique, where we only store dp values of the last 2 rows. Now let's see how many states would be used. Let the number of possible cases, where there is a row with N cells and each cell being described by taken or not taken, with a constraint that adjacent cells could not be taken simultaneously, be F( N ). By considering whether or not to take the first cell, it is clear that F( N ) = F( N - 1 ) + F( N - 2 ). Thus, we know that there are at most Fibonacci( 22 ) < 20000 possible states. Now we will only visit through these states, and call a DFS each time to update all possible successive states.
Time / Space Complexity:
O( N * 2^N ) / O( 2^N )
int N; vvi G; void init(){ cin >> N; G = vvi( N, vi( N ) ); for( int i = 0; i < N; ++i ){ for( int j = 0; j < N; ++j ){ cin >> G[ i ][ j ]; } } } int dp[ 2 ][ 1 << 22 ]; vi state; void dfs( const int f, const int ps, int s, int x, int v ){ if( x == N ){ upmax( dp[ ~f & 1 ][ s ], dp[ f & 1 ][ ps ] + v ); return; } if( x == 0 ){ if( ( ps & ( 1 << 2 ) - 1 ) == 0 ){ dfs( f, ps, s | 1 << x, x + 1, v + G[ f ][ x ] ); } } else if( ~s & 1 << x - 1 ){ if( ( ps & ( 1 << 3 ) - 1 << x - 1 ) == 0 ){ dfs( f, ps, s | 1 << x, x + 1, v + G[ f ][ x ] ); } } dfs( f, ps, s, x + 1, v ); } void preprocess(){ for( int s = 0; s < 1 << N; ++s ){ int invalid = 0; for( int i = 0; i + 1 < N; ++i ){ invalid |= s >> i & 1 and s >> i + 1 & 1; } if( invalid ) continue; state.emplace_back( s ); } for( int i = 0; i < N; ++i ){ memset( dp[ ~i & 1 ], 0, sizeof( dp[ ~i & 1 ] ) ); for( int j = 0; j < state.size(); ++j ){ dfs( i, state[ j ], 0, 0, 0 ); } } } void solve(){ cout << *max_element( dp[ N & 1 ], dp[ N & 1 ] + ( 1 << N ) ) << endl; }