测试结果 code:

#include<iostream>
#include<vector>
using namespace std;
vector<long long>dp[10][1025];//lineNumber|stateNumber|kingNumber
vector<int>state;
vector<int>kingSum;
int N, K;
void AllState(int deepth, int s, int sum) {
	if (deepth >= N) {
		kingSum.push_back(sum);
		state.push_back(s);
	} else {
		AllState(deepth + 2, s + (1 << deepth), sum + 1);
		AllState(deepth + 1, s, sum);
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K;
	AllState(0, 0, 0);
	for (int i = 0; i <= N; i++)
		for (int j = 0, len = state.size(); j < len; j++)
			dp[i][j].assign(K + 1, 0);
	for (int stateNumber = 0; stateNumber < kingSum.size(); stateNumber++)
		dp[1][stateNumber][kingSum[stateNumber]] = 1;
	for (int lineNumber = 2; lineNumber <= N; lineNumber++)
		for (int stateBefore = 0, len = state.size(); stateBefore < len; stateBefore++)
			for (int stateNow = 0 ; stateNow < len; stateNow++) {
				if ((state[stateBefore] << 1) & state[stateNow])
					continue;
				if (state[stateBefore]&state[stateNow])
					continue;
				if (state[stateBefore] & (state[stateNow] << 1))
					continue;
				for (int kingNumber = kingSum[stateNow] + kingSum[stateBefore]; kingNumber <= K; kingNumber++) {
					dp[lineNumber][stateNow][kingNumber] +=
					dp[lineNumber - 1][stateBefore][kingNumber - kingSum[stateNow]];
				}
			}
	long long Ans = 0;
	for (int stateNumber = 0, len = state.size(); stateNumber < len; stateNumber++)
		Ans += dp[N][stateNumber][K];
	cout << Ans;
	return 0;
}