T30191: SCOI2005 互不侵犯

状压dp, http://cs101.openjudge.cn/practice/30191/

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

输入

只有一行，包含两个数 N, K 。1 <= N <=9, 0 <= K <= N * N

输出

所得的方案数。

样例输入

3 2

样例输出

提示

DP, 状态压缩

来源

2025fall-cs101 yan. https://oi-wiki.org/dp/state/

【陈子良 25物理学院】状压dp从原理上说，与普通的dp没什么区别，只是其中某个维度的状态数可能非常大，是指数量级，此时我们可以通过二进制，用一个整数表示集合的状态。比如本题用整数a记录某一行摆放国王的方式，a的二进制中第i位为1表示该行第i位摆放一个国王。

初学状压dp时，我的感觉就是爽，平常dfs半天的题，直接用dp一遍推完就行了。但是爽又不能完全爽，因为每次都遍历 $2^{N}$ 个数会TLE，我们要先选出那些满足条件的状态，记录到state中，具体要求是：首先国王不能相邻，即a的二进制中不能有相邻两项为1，用二进制表示是a&(a<<1)==0；其次由于总的国王数为K，某一行的国王数不能超过K。这样得到的有效单行状态数设为M。

接下来判断相邻两行a与b的冲突情况。如果a的上一行是b,那么b中的国王能攻击到其正下方、左下方和右下方的格子，也就是b|(b<<1)|(b>>1)，我们要求a的所有国王不能被攻击，因此a&(b|(b<<1)|(b>>1))==0。我们把结果存储到M*M的矩阵conflict中，conflict[a][b]=conflict[b][a]，如果为True表示a与b可以相邻，反之不能相邻。

接下来建立递推关系。用dp[n][m][i]表示在棋盘的前n行放置m个国王，其中最后一行状态为a=state[i]时的摆放方案数，其中n方向是滚动的。对于第n行，我们遍历可能的摆放方案a=state[i]，a中含有k个国王，那么对于所有可能的、与a不冲突的上一行状态b=state[j]，若b前面共有m个国王，那么加上a后就总共有m+k个国王，从而dp[n][k+m][i]+=dp[n-1][m][j]。滚动到最后一行，把所有k==K的方案数加起来即可。

python

N,K=map(int,input().split())
def num(a):
	# 状态a中的国王数
    return bin(a).count('1')
# 存储所有单行合法的状态
state=[]
for a in range(1<<N):
    if a&(a<<1):
        continue
    k=num(a)
    if k>K:
        continue
    state.append(a)
M=len(state)
# 存储相邻两行合法的状态
conflict=[[False]*M for _ in range(M)]
for i in range(M):
    for j in range(M):
        a=state[i]
        b=state[j]
        if a&b==0 and a&(b<<1)==0 and a&(b>>1)==0:
            conflict[i][j]=True
dp=[[0]*M for _ in range(K+1)]
for i in range(M):
    a=state[i]
    dp[num(a)][i]=1
for _ in range(N-1):
    dp1=[[0]*M for _ in range(K+1)]
    for i in range(M):
        a=state[i]
        k=num(a)
        for m in range(K+1-k):
            for j in range(M):
                if conflict[i][j]:
                    dp1[k+m][i]+=dp[m][j]
    dp=dp1
print(sum(dp[-1]))

T30191: SCOI2005 互不侵犯 ​

T30191: SCOI2005 互不侵犯