Introduction to Compressed Dynamic Programming

Introduction to State Compression Dynamic Programming#

State compression is the process of representing a continuous chunk of states that can be represented using 01 in 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 using 01, so the state of each row can be represented using an integer.

First, preprocess all the cases in a row where there are no fights, and the corresponding number of kings for each case.

f[i][j][k] represents the number of solutions when the state of the ith row is the jth type 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 one bit can check if there are adjacent 1s, but right shifting 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) {// i-th row
    for (let j = 1; j <= newg; ++j) {// state of this row
        for (let l = 0; l <= k; ++l) {// total number of kings used up to this row
            if (l >= kingCnt[j]) {
                for (let m = 1; m <= newg; ++m) {// state of the previous row
                    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)
});