BZOJ 1087: [SCOI2005]互不侵犯King

题目描述

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

Input

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

Output

　　方案数。

Sample Input

3 2

Sample Output

16

显然是个状压dp
对每一行国王的摆放方式状压，设dp[i][j][k]表示到了第i行，第i行的摆放情况是j，总共摆了k个（包括第i行）
枚举行号，枚举这一行状态，枚举总数，枚举上一行的状态，转移时判一下合不合法，用sta表示状态
首先，对于一行，不能有相邻的，！(（sta & (sta << 1）） || ( sta & (sta >> 1) ) )
上下两行之间 !( (sta1 & sta2) || (sta1 & (sta2 << 1) ) || (sta1 & (sta2 >> 1)) )
如果有人想精益求精的话可以预处理出来，反正对于每一行都是一样的。
最后，方案数炸int（别问我怎么知道。。）

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
inline int read()
{
    register int x = 0 , f = 0; register char c = getchar();
    while(c < ‘0‘ || c > ‘9‘) f |= c == ‘-‘ , c = getchar();
    while(c >= ‘0‘ && c <= ‘9‘) x = (x << 3) + (x << 1) + c - ‘0‘ , c = getchar();
    return f ? -x : x;
}
int n , k;
LL dp[10][1<<9|1][82];
 
inline int check(int sta) { return !((sta & (sta << 1)) || (sta & (sta >> 1))); }
inline int check(int sta1 , int sta2) { return !((sta1 & sta2) || ((sta1 << 1) & sta2) || ((sta1 >> 1) & sta2)); }
inline int Count(int sta)
{
    int res = 0;
    for(int i = 1 ; i <= n ; ++i) res += (sta >> (i - 1)) & 1;
    return res;
}
 
int main()
{
    n = read(); k = read();
    dp[0][0][0] = 1;
    for(int i = 1 ; i <= n ; ++i) // 行号 
        for(int j = 0 ; j < (1 << n) ; ++j) if(check(j)) // 这一行状态 
            for(int l = 0 ; l < (1 << n) ; ++l) if(check(l) && check(j , l)) // 上一行状态 
                for(int s = 0 ; s <= k ; ++s) // 总个数
                {
                    int c = Count(j) , d = Count(l); if(s < c + d) continue;
                    dp[i][j][s] += dp[i-1][l][s - c];
                }
    LL ans = 0;
    for(int i = 0 ; i < (1 << n) ; ++i) ans += dp[n][i][k];
    cout << ans << ‘\n‘;
    return 0;
}
?```

BZOJ 1087: [SCOI2005]互不侵犯King

原文：https://www.cnblogs.com/R-Q-R-Q/p/12700925.html