Introduction to Compressed Dynamic Programming

Oct 23, 2019#动态规划64

AI Translation

This post is translated from Chinese into English through AI.View Original

AI-generated summary

Introduction to state compression dynamic programming, using integers to represent continuous states that can be expressed as 01, and performing operations using bitwise operations. Example problem involves representing the distribution of kings in each row using integers. Preprocess to find all non-conflicting scenarios in a row and corresponding number of kings. Use dynamic programming to calculate the number of ways for each row's state. Code provided in Node.js.

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

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