首页 > 代码库 > [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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。