互不侵犯

题目描述

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

注：数据有加强（2018/4/25）

输入输出格式

输入格式：

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

输出格式：

所得的方案数

输入输出样例

输入样例#1：
3 2
输出样例#1：
16

这道题是状压(dp)入门题的第二题，也就是说，不算很难。~~本蒟蒻做了一个小时~~

言归正传

我们设(dp)方程(dp[i][j][k])表示第(i)行第(j)种状态(k)个国王，然后转移方程(dp[i][j][k]+=dp[i-1][o][k-sum[j]])
那么我们怎么判断他们都互相不在攻击范围之内呢？那肯定就是一系列的位运算了。下面就不多说，代码写的很清楚了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,k;
long long dp[10][5000][1000],state[5000],tot,sum[5000];
void work_1(int he,int s,int node) {
    long long p = 1<<n;
    for(int i=0;i<p;i++)
        if(!(i&(i<<1))){
            state[++tot]=i;
            sum[tot]=__builtin_popcount(i);
        }
}
int main() {
    scanf("%d%d",&n,&k);
    work_1(0,0,0);
    for(int i=1; i<=tot; i++)
        dp[1][i][sum[i]]=1;
    for(int i=2; i<=n; i++)
        for(int j=1; j<=tot; j++)
            for(int o=1; o<=tot; o++) {
                if(state[j]&state[o]) continue;
                if((state[j]<<1)&state[o])continue;
                if(state[j]&(state[o]<<1))continue;
                for(int s=sum[j];s<=k;s++)dp[i][j][s]+=dp[i-1][o][s-sum[j]];
            }
    long long ans=0;
    for(int i=1; i<=tot; i++) 
        ans+=dp[n][i][k];
    printf("%lld",ans);
}

互不侵犯_状压$dp$