1087: [SCOI2005]互不侵犯King
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4595 Solved: 2664
[Submit][Status][Discuss]
Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
Sample Output
分析：
老套路，预先处理出一行内合法方案，减少枚举数。
定义状态f[i][j][k]第i行，状态为j，目前一共放了k个国王，转移走就行了。
AC代码：
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
const int N = << ;
int cnt,state[],num[],P,n,c;
long long f[][][];
int lowbit(int r){
return r & -r;
}
void work(){
for(int i = ;i < P;i++){
int pre = lowbit(i),r = i - pre;bool flag = true;
while(r){
if(lowbit(r) / pre <= ){
flag = false;break;
}
pre = lowbit(r);r -= pre;
}
if(flag)state[++cnt] = i;
}
for(int i = ;i <= cnt;i++){
int r = state[i];
while(r){
r -= lowbit(r);
num[i]++;
}
}
}
int main(){
scanf("%d %d",&n,&c);P = << n;
work();
f[][][] = 1LL;
for(int i = ;i <= n;i++){
for(int j = ;j <= cnt;j++){
for(int k = ;k <= cnt;k++){
for(int l = ;l <= c;l++){
if(state[j] & state[k])continue;
if((state[j] >> ) & state[k])continue;
if((state[j] << ) & state[k])continue;
f[i][j][l + num[j]] += f[i - ][k][l];
}
}
}
}
long long ans = ;
for(int i = ;i <= cnt;i++){
ans += f[n][i][c];
}
printf("%lld\n",ans);
}