萌新求调

#include <bits/stdc++.h>
using namespace std;
int n,k;
int f[20][1<<9+5][90];//f[i][st][j]表示第i行的状态为st，到第i行总共放置了j个国王
int c(int x) { //返回的是二进制中1的个数
	int sum=0;
//	cout << x << " ";
	while(x) {
		sum+=x%2;
		x/=2;
	}
	//cout << sum << "\n";
	return sum;
}
bool check1(int st) { //判断本行内是否有国王相邻
	for(int i=1; i<n; i++) {
		if((st>>i)&1&&(st>>(i-1))&1) { //如果有国王相邻，返回false
			return false;
		}
	}
	return true;
}
bool check2(int st1,int st2) { //判断第i行与第i-1行是否符合
	for(int i=1; i<=n; i++) {
		if((st1>>i)&1&&(st2>>(i-1))&1) return false;
		if((st1>>i)&1&&(st2>>(i))&1) return false;
		if((st1>>i)&1&&(st2>>(i+1))&1) return false;
	}
	return true ;
}
int main () {
	cin >> n >> k;
	for(int i=1; i<=n; i++) {
		for(int st=0; st<(1<<n); st++) {
			if(!check1(st))
				continue;
			if (i==1)
				f[i][st][c(st)]=1;
			else
				for(int j=c(st); j<=k; j++) {
					for(int st2=0;st2<(1<<n);st2++){
						if(check1(st2)&&check2(st,st2)){
							f[i][st][j]+=f[i-1][st2][j-c(st)];
						}
					}
				}
		}
	}
	int sum=0;
	for(int st=0;st<(1<<n);st++){
		sum+=f[n][st][k];
	}
	cout << sum;
	return 0;
}