狀壓dp入門 - BuringStraw

狀壓 dp 入門#

狀態壓縮嘛，就是把連續的一塊可以用 01 表示的狀態，搞進個整數裡，然後用位運算來進行檢查、轉移等操作。

例題#

[SCOI2005] 互不侵犯

每行國王分佈的情況可以用 01 表示，這樣就可以把每一行的狀態用一個整數表示。

先預處理出一行裡面沒有會打架的所有情況，和該情況對應的國王數量

f[i][j][k]為第i行的狀態為第j種時，一共用了k個國王的方案數

那麼f[i][j][k]=f[i - 1][l][k - kingCnt[l]]

具體看代碼。

這次用了nodejs來寫，寫完之後頓時感覺c++是最好的語言

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 //數值最大的狀態
  let goodI = new Array(513).fill(0), kingCnt = new Array(513).fill(0) //能用的狀態和它對應的國王數量
  let newg = 0
  for (let i = 0; i <= maxI; ++i) {
      if (i & (i << 1)) continue //左移或右移一位都能看有沒有相鄰的兩個1，但是右移最低位的1就沒了
      ++newg;
      goodI[newg] = i
      for (let j = 0; j < n; ++j) {
          if (i & (1 << j)) {//看看那些位上有1
            ++kingCnt[newg]
          }
      }
  }

  //我淦，為什麼初始化數組這麼麻煩？
  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)
    }
  }

  //初始化，題解裡面我看得懂的一個
  for (let i = 1; i <= newg; ++i) {
    if (kingCnt[i] <= k) {//如果這種狀態要的國王數量小於k，那他就是一種解
      f[1][i][kingCnt[i]] = 1
    }
  }
  for (let i = 1; i <= n; ++i) {//第i行
    for (let j = 1; j <= newg; ++j) {//本行狀態
        for (let l = 0; l <= k; ++l) {//本行為止總共用到的國王
            if (l >= kingCnt[j]) {
                for (let m = 1; m <= newg; ++m) {//上一行狀態
                    if (!(goodI[m] & goodI[j]) && 
                    !(goodI[m] & (goodI[j] << 1)) &&
                    !(goodI[m] & (goodI[j] >> 1))) {//判斷
                        f[i][j][l] = f[i - 1][m][l - kingCnt[j]] + f[i][j][l]//轉移
                    }
                }
            }
        }
    }
  }
  for (let i = 1; i <= newg; ++i) {//可能在任意一行結尾
      ans = f[n][i][k] + ans
  }
  process.stdout.write(`${ans}\n`)
  process.exit(0)
});