0w1

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;
}