状压 DP


定义

状压 DP 是动态规划的一种,通过将状态压缩为整数来达到优化转移的目的。

例题

的棋盘里面放 个国王(),使他们互不攻击,共有多少种摆放方案。

国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共 个格子。

解释

表示前 行,第 行的状态为 ,且棋盘上已经放置 个国王时的合法方案数。

对于编号为 的状态,我们用二进制整数 表示国王的放置情况, 的某个二进制位为 表示对应位置不放国王,为 表示在对应位置上放置国王;用 表示该状态的国王个数,即二进制数 的个数。例如,如下图所示的状态可用二进制数 来表示(棋盘左边对应二进制低位),则有

设当前行的状态为 ,上一行的状态为 ,可以得到下面的状态转移方程:

设上一行的状态编号为 ,在保证当前行和上一行不冲突的前提下,枚举所有可能的 进行转移,转移方程:

实现

#include <algorithm>
#include <iostream>
using namespace std;
long long sta[2005], sit[2005], f[15][2005][105];
int n, k, cnt;

void dfs(int x, int num, int cur) {
  if (cur >= n) {  // 有新的合法状态
    sit[++cnt] = x;
    sta[cnt] = num;
    return;
  }
  dfs(x, num, cur + 1);  // cur位置不放国王
  dfs(x + (1 << cur), num + 1,
      cur + 2);  // cur位置放国王,与它相邻的位置不能再放国王
}

bool compatible(int j, int x) {
  if (sit[j] & sit[x]) return false;
  if ((sit[j] << 1) & sit[x]) return false;
  if (sit[j] & (sit[x] << 1)) return false;
  return true;
}

int main() {
  cin >> n >> k;
  dfs(0, 0, 0);  // 先预处理一行的所有合法状态
  for (int j = 1; j <= cnt; j++) f[1][j][sta[j]] = 1;
  for (int i = 2; i <= n; i++)
    for (int j = 1; j <= cnt; j++)
      for (int x = 1; x <= cnt; x++) {
        if (!compatible(j, x)) continue;  // 排除不合法转移
        for (int l = sta[j]; l <= k; l++) f[i][j][l] += f[i - 1][x][l - sta[j]];
      }
  long long ans = 0;
  for (int i = 1; i <= cnt; i++) ans += f[n][i][k];  // 累加答案
  cout << ans << endl;
  return 0;
}

习题

贡献者:@TianKong_y@WenzelTian@Legendary-Zeraora@Shuhao@kenlig@ZHB@REYwmp@mgt@sshwy@H-J-Granger@Henry-ZHR@ouuan@雷蒻@Trisolaris@Ir1d@Chro@Xeonacid@Mosa-Linking

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组