洛谷P1896-互不侵犯(状压dp)

题意：洛谷P1896

在$N\times N$的棋盘里面放$K$个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共$8$个格子。$(N<=9,K<=N\ast N)$

分析：

首先暴搜肯定被否定，时间复杂度是指数级的，所以我们就可用上状态压缩$dp$啦。

那什么是状态压缩？在这题中按照我的理解就是将一行的所有摆放状态看成不同的$01$串，然后将这些$01$串看成二进制数，这样每一个摆放状态就有一个$01串$(二进制数)与其对应。 假设$1$行有$4$个格子，我们在第$1、3$个格子放棋子，$2、4$不放棋子，然后我们定义一个$01$串${}^{\prime }{1}^{\prime }$表示此处有棋子，${}^{\prime }{0}^{\prime }$表示没有棋子，那么这个$01$串就是$1010$。那么这样子做有什么好处？我的答案是操作起来十分方便和节省空间。为什么方便？因为二进制下对于这些状态运用位运算十分好操作。

对于这题我们如何操作？我们可以先预处理第一行的所有可行状态以及可行状态$can[i]$所需的棋子数$num[i]$，然后根据题目所给条件一直往下递推。

转移方程:$dp[i][j][l]+=dp[i-1][p][l-num[j]]$。 其中$i$是当前行，$j$是当前状态，$p$是上一行的可行状态，$l$是当前状态所需的棋子数，所以$l$从$l-num[j]$而来。

如何判断题目所给的$8$个方向上是否有冲突？因为我们是从上往下递推，所以在考虑当前行时仅用考虑此格子的上下左右和左上右上，不需要考虑左下右下。 我们同样可以预处理一行中的所有状态，将相邻的状态全部否定，那么我们在递推的时候就不用考虑这些状态了。考虑位运算。 假设上一行状态$y$，本行状态$x$。 同行的判断：如果一个二进制数$x$有相邻的$1$(棋子)，那么 $(x<<1)\&x$ 必定不等于$0$。 左上右上的判断：我们直接让$x$左移或右移一位再$\&$上$y$如果不等于$0$则冲突。$((x<<1)\&y)$ $!=0$，$((x>>1)\&y)$ $!=0$。 正上方的判断：$(x\&y)$ $!=0$ 递推完后，我们加上最后一行摆放有$k$个子的状态的方案数就好了。 知道了这些这题就很简单 了。

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, k, maxsta; ll ans, num[1 << 10], dp[10][1 << 10][10 * 10]; bool can[1 << 10]; int main(){ cin >> n >> k; maxsta = (1 << n); for(int i = 0; i < maxsta; i++) if((i & (i << 1)) == 0) can[i] = true;//同行是否有相邻的判断 for(int i = 0, temp; i < maxsta; i++){ temp = i; if(can[temp]){//预处理可行状态所需的棋子数 while(temp){ num[i] += temp % 2 == 1; temp >>= 1 ; } } } for(int i = 0; i < maxsta; i++) if(can[i] && num[i] <= k) dp[1][i][num[i]] = 1;//预处理第一行 for(int i = 2; i <= n; i++){ for(int j = 0; j < maxsta; j++){//本行 if(can[j]){ for(int p = 0; p < maxsta; p++){//上一行 if(!can[p]) continue; if((j & p) != 0) continue; if(((j << 1) & p) != 0) continue; if(((j >> 1) & p) != 0) continue; for(int l = num[j]; l <= k; l++) dp[i][j][l] += dp[i - 1][p][l - num[j]]; } } } } for(int i = 0; i < maxsta; i++) ans += dp[n][i][k]; cout << ans << '\n'; return 0; }

蒟蒻的第一题状压$dp$，不容易啊。