小国王 骑士 状态压缩DP

// 小国王.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>


using  namespace  std;

/*
https://loj.ac/p/10170
http://ybt.ssoier.cn:8088/problem_show.php?pid=1592
在 n x n 的棋盘上放 k 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。

输入格式
只有一行，包含两个整数 n 和 k。

输出格式
每组数据一行为方案总数，若不能够放置则输出 0。

输入
3 2
输出
16

输入
4 4
输出
79

对于全部数据，1 <= n <=  10, 0 <=  k <= n^2。
*/
const int N = 12;
long long dp[N][105][1 << N];
int n, t;


int getOne(int x) {
	int ret = 0;
	while (x != 0) {
		ret++;
		x -= (x & -x);
	}

	return ret;
}

//检查是否有连续两个1
bool check2(int x) {
	int state = 0;
	while (x != 0) {
		if (x & 1 && state == 1) return true;
		state = x & 1;
		x >>= 1;
	}

	return false;
}

bool check(int a, int b) {
	if ( (a & b) != 0) 
		return false;
	if (check2(a) || check2(b) || check2(a | b)) 
		return false;
	return true;
}

vector<int> state[1 << N];
//预处理所有可以转移的状态
void gen(int n) {
	for (int i = 0; i < 1 << n; i++) {
		for (int j = 0; j < 1 << n; j++) {
			if (check(i, j)) {
				state[i].push_back(j);
			}
		}
	}
}


int main() {
	cin >> n >> t;

	gen(n);

	dp[0][0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int k = 0; k <= t; k++) {
			for (int prev = 0; prev < 1 << n; prev++) {
				for (auto& curr : state[prev]) {
					int oneNum = getOne(curr);
					if (oneNum + k <= t) {
						dp[i][oneNum + k][curr] += dp[i - 1][k][prev];
					}
				}
			}
		}
	}


	long long ans = 0;
	for (int i = 0; i < 1 << n; i++) {
		ans += dp[n][t][i];
	}
	cout << ans << endl;


	return 0;
}