在清北学堂DP&Graph班里学到了这一题，状压DP的入门题目

<h1>题目描述</h1>

<h2>题目背景</h2>

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

<h2>输入输出格式</h2>

<h3>输入格式：</h3>

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

<h3>输出格式：</h3>

所得的方案数

<h2>样例</h2>

<h3>样例输入</h3>

3 2

<h3>样例输出</h3>

16

<h1>思路</h1>

看到这一题，首先就应该想到搜索和DP，显然暴力是不可取的。
则我们考虑DP。
设$ f[i][j][k] $表示到第i行第j列合法时已经摆放了$ k $个King时的方案数。
我们设$ status[i] $来记录一个二进制数来表示状态（第$ j $位为1的时候表示这一列有国王，反之则没有）。
$ cnt[i] $记录第i中情况有多少个1.
DP的话我们可以按照行进行状态压缩，这样即可得到一个状态转移方程：
$$ f[i][l][status[k]] = f[i][l][status[k]] + f[i-1][l-cnt[j]][status[j]] $$

当 $$ status[j] \&amp; status[k] = 0, status[j] \&amp; (status[k] &lt;&lt; 1) = 0,status[j] \&amp; status[k] >> 1 = 0 $$
边界情况：$ f[1][cnt[i]][i] = 1 $

<h1>代码实现</h1>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],p1=buf+BUF_SIZE,pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='n'||ch=='r'||ch=='t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};
using namespace fastIO;

const int MAXN = 9+1;
#define lowbit(x) (x&-x)
int status[(1<<MAXN)+1],cnt[(1<<MAXN)+1],size;
/// status 合法的情况，cnt 情况有多少个二进制1 
LL fMAXN[(1<<MAXN)+1];
int N,K;

int main(){
    read(N);read(K);
    int MAX = (1<<N)-1;
    FOR(i,0,MAX){
        if(i & (i>>1)) continue;
        status[++size] = i;
        int x = i;
        while(x){
            x -= lowbit(x);
            cnt[size]++;
        }
    }
    FOR(i,1,size) f1][i] = 1;
    FOR(i,2,N){
        FOR(j,1,size){
            FOR(k,1,size){
                if((status[j]&status[k]) || (status[j]&status[k] << 1) || (status[j]&status[k] >> 1)) continue;
                FOR(l,cnt[k],K){
                    fi[k] += fi-1][j];
                }
            }
        }
    }
    LL ans=0;
    FOR(i,1,size) ans += fN[i];
    printf("%lldn",ans);
    return 0;
}