题目：互不侵犯King
思路：位运算+记忆化搜索
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
using namespace std;#define ll long longint n,k;
int num[100]={0}; //状态i中国王的个数，-1表示改状态会出现有国王相邻 ll f[10][1<<10][100]={0}; //层数、状态、国王数 ll dfs(int step,int state,int s){if(step==n) {if(s==k) return 1;return 0; }ll x=0;for(int i=0;i<(1<<n);i++){if(num[i]!=-1&&num[i]+s<=k&&!(i&state)&&!(i&(state<<1))&&!(i&(state>>1))){if(f[step+1][i][num[i]+s]) {x+=f[step+1][i][num[i]+s];continue;}f[step+1][i][num[i]+s]=dfs(step+1,i,s+num[i]);x+=f[step+1][i][num[i]+s];}}return x;
}int judge(int x){int y=x,t=0,s=0;while(y){if(t==1&&(y&1)) return -1;t=y&1;if(t==1) s++;y>>=1;}return s;
}int main() {scanf("%d%d",&n,&k);for(int i=0;i<(1<<n);i++){num[i]=judge(i);}printf("%lld",dfs(0,0,0));return 0;
}