状圧 dp 入門#
状態圧縮とは、連続した一塊の状態を 01 で表現し、それを整数に格納し、ビット演算を用いてチェック、遷移などの操作を行うことです。
例題#
各行の王の分布は 01 で表現できるため、各行の状態を 1 つの整数で表すことができます。
まず、1 行の中で戦うことのないすべての状態と、その状態に対応する王の数を前処理します。
f[i][j][k]は第i行の状態が第j種のとき、合計でk個の王を使用した場合の方案数です。
したがって、f[i][j][k]=f[i - 1][l][k - kingCnt[l]]となります。
具体的にはコードを見てください。
今回は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 //左移動または右移動で隣接する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未満であれば、それは解の1つです
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)
});