Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16
状压DP, 状态压成二进制01串,0,1分别表示无king,有king;
状态:f[i][j][k], 到第i行, 放了j个king, 此时状态为k的方案数;
预处理:合法状态(isleg1),合法相邻状态(isleg2);
代码:
1 //互不侵犯King SCOI2005__From BZOJ 1087 2 #include<iostream> 3 #include<cstdio> 4 typedef long long ll; 5 6 int n, m, maxs, arr[1024]; 7 ll f[10][100][1024], ans; 8 bool isleg1[1024], isleg2[1024][1024]; 9 10 int main() 11 { 12 std::cin >> n >> m; 13 maxs = (1 << n) - 1; 14 for(int i = 0; i <= maxs; i++) 15 if(!(i&(i >> 1)))//错位&,若有两个连着的1则结果不为0 16 { 17 int tmp = i; 18 isleg1[i] = 1; 19 while(tmp) 20 { 21 if(tmp&1) arr[i]++; 22 tmp >>= 1; 23 } 24 } 25 for(int i = 0; i <= maxs; i++)//处理可以相邻的状态 26 if(isleg1[i]) for(int j = 0; j <= maxs; j++) 27 if(isleg1[j]&&!(i&j)&&!(i&(j >> 1))&&!((i >> 1)&j)) 28 isleg2[i][j] = 1; 29 for(int i = 0; i <= maxs; i++)//预处理第一行的可行状态 30 if(isleg1[i]) f[1][arr[i]][i] = 1; 31 for(int i = 1; i < n; i++)//枚举该行为状态j时下一行的状态 32 for(int j = 0; j <= maxs; j++) 33 if(isleg1[j]) for(int k = 0; k <= maxs; k++) 34 if(isleg1[k]&&isleg2[j][k]) 35 for(int t = arr[j]; t + arr[k] <= m; t++) 36 f[i + 1][t + arr[k]][k] += f[i][t][j]; 37 for(int i = 0; i <= maxs; i++) 38 ans += f[n][m][i]; 39 std::cout << ans; 40 return 0; 41 }