Introduction to Compressed Dynamic Programming

Introduction to State Compression DP#

So, state compression is about putting a bunch of consecutive states that can be represented by 01 into an integer, and then using bitwise operations to perform checks, transitions, and other operations.

Example Problem#

[SCOI2005] Non-Interference

The distribution of kings in each row can be represented by 01, so the state of each row can be represented by an integer.

First, preprocess all the situations in a row where there are no fights, and the corresponding number of kings in that situation.

f[i][j][k] represents the number of solutions where the state of the ith row is the jth kind and k kings are used.

See the code for details.

This time I used nodejs to write, and after finishing it, I suddenly felt that c++ is the best language.

Code#

process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('readable', () => {
  let line  = process.stdin.read()
  if (line == null) {
    return
  }
  line = line.split(' ')
  let n = parseInt(line[0]), k = parseInt(line[1])
  let ans = 0
  let maxI = (1 << n) - 1 // maximum state value
  let goodI = new Array(513).fill(0), kingCnt = new Array(513).fill(0) // usable states and their corresponding number of kings
  let newg = 0
  for (let i = 0; i <= maxI; ++i) {
      if (i & (i << 1)) continue // left or right shift by one bit can check if there are adjacent 1s, but right shift loses the lowest 1
      ++newg;
      goodI[newg] = i
      for (let j = 0; j < n; ++j) {
          if (i & (1 << j)) {// check which bits have 1
            ++kingCnt[newg]
          }
      }
  }

  // Why is initializing arrays so complicated?
  let f = new Array(10);
  for (i = 0; i < 11; ++i) {
    f[i] = new Array(513)
    for (j = 0; j < 160; ++j) {
      f[i][j] = new Array(82).fill(0)
    }
  }

  // Initialization, one that I can understand in the solution
  for (let i = 1; i <= newg; ++i) {
    if (kingCnt[i] <= k) {// if the number of kings required for this state is less than k, then it is a solution
      f[1][i][kingCnt[i]] = 1
    }
  }
  for (let i = 1; i <= n; ++i) {// the i-th row
    for (let j = 1; j <= newg; ++j) {// current row state
        for (let l = 0; l <= k; ++l) {// total number of kings used so far
            if (l >= kingCnt[j]) {
                for (let m = 1; m <= newg; ++m) {// previous row state
                    if (!(goodI[m] & goodI[j]) && 
                    !(goodI[m] & (goodI[j] << 1)) &&
                    !(goodI[m] & (goodI[j] >> 1))) {// check
                        f[i][j][l] = f[i - 1][m][l - kingCnt[j]] + f[i][j][l]// transition
                    }
                }
            }
        }
    }
  }
  for (let i = 1; i <= newg; ++i) {// can end in any row
      ans = f[n][i][k] + ans
  }
  process.stdout.write(`${ans}\n`)
  process.exit(0)
});