状態圧縮 DP 入門#
状態圧縮とは、01 で表現できる連続した状態を整数に詰め込み、ビット演算を使用してチェックや転送などの操作を行うことです。
問題例#
国王の配置は、01 で表現できますので、各行の状態を整数で表現することができます。
まず、衝突しない状態とその状態に対応する国王の数を事前に処理します。
f[i][j][k]は、第i行の状態が第j種類であり、合計でk個の国王を使用する場合の数です。
具体的なコードを見てください。
今回はnodejsを使用していますが、コードを書いた後、c++が最も優れた言語であると感じました。
コード#
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ビットで隣り合う2つの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)
});