首页 > 代码库 > [luoguP1896] [SCOI2005]互不侵犯King(状压DP)

[luoguP1896] [SCOI2005]互不侵犯King(状压DP)

传送门

 

先预处理出来一行中放置国王的所有情况和每种情况所用的国王个数。

f[i][j][k]表示前i行放j个国王且最后一行的状态为k的方案数

状压DP即可

#include <cstdio>#define N 1001int n, m, cnt, ans;int a[N][2], f[10][82][N];inline void dfs(int s, int k, int last){	if(k > m) return;	int i, j;	cnt++;	a[cnt][0] = s;	a[cnt][1] = k;	for(i = last + 1; i <= n; i++)		if(!(s & (1 << i - 1)) && !(s & (1 << i)) && !(s & (1 << i + 1)))			dfs(s | (1 << i), k + 1, i);}inline bool check(int x, int y){	return !(a[x][0] & a[y][0]) && !(a[x][0] & (a[y][0] << 1)) && !(a[x][0] & (a[y][0] >> 1));}int main(){	int i, j, k, l;	scanf("%d %d", &n, &m);	if(m > (n + 1) / 2 * (n + 1) / 2)	{		puts("0");		return 0;	}	dfs(0, 0, 0);	f[0][0][1] = 1;	for(i = 1; i <= n; i++)		for(j = 0; j <= m; j++)			for(k = 1; k <= cnt; k++)				for(l = 1; l <= cnt; l++)					if(j + a[l][1] <= m && check(k, l))						f[i][j + a[l][1]][l] += f[i - 1][j][k];	for(i = 1; i <= cnt; i++) ans += f[n][m][i];	printf("%d\n", ans);	return 0;}

  

[luoguP1896] [SCOI2005]互不侵犯King(状压DP)