题解 | #[SCOI2005]互不侵犯KING#

今天刚刚学状压DP先来了手入门哈哈哈，效率可能没有那么高。

dp的定义dp[i][t][k] 第 i 行状态为 t 且放置 KING 的数目为 k 的方案数。

遍历第i行的状态值t从0开始到((1 << N) - 1) 如果 (t << 1) & t不为0说明有king放置在了一起

然后从0 到 ((1 << N) - 1)遍历合法的上一行状态 如果不合法就continue掉 上一行与当行不合法状态为

(pj << 1) & pj) || ((pj & j) || ((pj << 1) & j) || ((pj >> 1) & j)

对整体取非 则如果这个条件成立就说明不合法continue掉

然后更新k值就可以啦

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<utility>

#define pb push_back 

using namespace std;
typedef long long ll;

// __builtin_popcount() 计算32位有多少个1

ll dp[15][(1 << 9) + 10][88]; // dp[i][t][k] 表示第i行状态位t放置了k个King的方案

void solve(int _) {
	int N, K; scanf("%d%d", &N, &K);
	memset(dp, 0, sizeof(dp));
	dp[0][0][0] = 1; // 初始化
	// 遍历 行数
	for(int i = 1; i <= N; i++) {
		// 遍历状态
		for(int j = 0; j <= ((1 << N) - 1); j++) {
			// 确保行合法
			// (j << 1) & j如果不为 0 说明存在非法状态
			if((j << 1) & j) {
				continue;
			}
 			// 遍历上一行的状态
			for(int pj = 0; pj <= ((1 << N) - 1); pj++) {
				// 保留可用的上一行状态 即合法状态且在该为选为king时本状态的上 上左 上右不能当选king
				if(((pj << 1) & pj) || ((pj & j) || ((pj << 1) & j) || ((pj >> 1) & j)) ) {
					continue;
				}
				// 遍历 k 这一行k的大小
				for(int k = __builtin_popcount(j); k <= K; k++) {
					dp[i][j][k] += dp[i - 1][pj][k - __builtin_popcount(j)];
				}
			}
		}
	}
	ll ans = 0;
	for(int i = 0; i <= (1 << N) - 1; i++) {
		ans += dp[N][i][K];
	}
	printf("%lld", ans);
}	

int main() {
	int _ = 1; 
	// scanf("%d", &_);
	int c = 1;
	while(c <= _){
		solve(c);
		c++;
	}
	return 0;
}