互不侵犯king (状压dp)

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

　　这道题如果普通dfs肯定会超时。为什么呢？我们发现一行中的状态是固定的，同时行与行之间的冲突情况也是固定的。而dfs重复枚举了每一行的状态，重复判断了这一行的状态是否与前一行相冲突。于是我们预处理出一行中的状态，同时预处理出两行状态的冲突情况，然后dp就行了。\(f[i][j][k]\)表示枚举到第i行，有j个国王，当前行状态的编号为k。它只能通过不与k冲突的上一行转移而来。于是就过了。

#include 
    
     using namespace std;long long st[100];int cnt[100], now[10], map[100][100];int n, k, cntst;long long f[10][100][100];void dfs(int pos){    now[pos]=1;    long long tmp=0; ++cntst;    for (int i=1; i<=n; ++i){        tmp=(tmp<<1)+now[i];        cnt[cntst]+=now[i];    }    st[cntst]=tmp;    for (int i=pos+2; i<=n; ++i) dfs(i);    now[pos]=0;}int main(){    scanf("%d%d", &n, &k);    st[0]=0; cnt[0]=0;    for (int i=1; i<=n; ++i) dfs(i);    for (int i=0; i<=cntst; ++i)        for (int j=0; j<=cntst; ++j)            if ((st[i]&st[j])==0&&            ((st[i]<<1)&st[j])==0&&            ((st[i]>>1)&st[j])==0){                map[i][j]=1; map[j][i]=1;            }    f[0][0][0]=1;    for (int i=1; i<=n; ++i)        for (int j=0; j<=k; ++j)            for (int st=0; st<=cntst; ++st){                if (cnt[st]>j) continue;                for (int st2=0; st2<=cntst; ++st2){                    if (!map[st][st2]) continue;                    f[i][j][st]+=f[i-1][j-cnt[st]][st2];                }            }    long long ans=0;    for (int i=0; i<=cntst; ++i)        ans+=f[n][k][i];    printf("%lld", ans);    return 0;}