【题目大意】
给定一个n*n的棋盘，求放置k个互不攻击的象的方法数。其中n <= 8，k <= n ^
2。
【题目分析】
对于棋盘放车问题可以用组合数学的知识来解决，但是对于含禁区的摆放问题，虽然组合数学给出了经典的棋盘多项式+容斥原理的解法，但是实际中棋盘多项式的求解是很困难的，因此一般需要借助状态压缩动态规划求解。
现在题目中要求出互不攻击的象的方法数，象的攻击路线是斜的，是不是可以考虑采用放车的方法来解呢？将棋盘黑白染色，如果一个象在黑色的格子里面，那么它一定不会攻击到白色的格子，这样的话可以分开计数，然后最后利用乘法原理加起来就行了。把棋盘旋转45度，这样象的攻击路线就是直的了，如果只考虑一种颜色的话，那么问题就转变成了经典的放车问题了，可以利用动态规划解决。
设dp[i][j]表示前i行放了j个车的方法数，c[i]表示第i行可以放置的棋子数量，那么转移方程为：
dp[i][j]
= dp[i-1][j] + dp[i-1][j-1] * (c[i] - (j -
1))
需要注意的是c数组应该是增序的，这样才能保证前面的j-1行放了车，对应这一行就有j-1个位置不可放了。
这个题目的dp方程不难想，但是如何把模型转化到放车问题是不容易想到的，尤其是将棋盘黑白染色后分开计数的想法，非常巧妙。
题目代码：
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4 const int N = 70;
5
6 void init(int n, int c1[N], int c2[N])
7 {
8 memset(c1, 0, sizeof(int) * N);
9 memset(c2, 0, sizeof(int) * N);
10 for (int i = 1; i <= n; i++)
11 {
12 for (int j = 1; j <= n; j++)
13 {
14 if ((i + j) & 1)
15 c2[(i+j)/2]++;
16 else
17 c1[(i+j)/2]++;
18 }
19 }
20 }
21 void bishops(int n, int dp[N][N], int c[N])
22 {
23 for (int i = 0; i <= n; i++)
24 dp[i][0] = 1;
25 for (int i = 1; i <= n; i++)
26 for (int j = 1; j <= c[i]; j++)
27 dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (c[i] - j + 1);
28 }
29
30 int main()
31 {
32 int n, k, c1[N], c2[N], dp1[N][N], dp2[N][N], ans;
33
34 while (scanf("%d %d", &n, &k) == 2)
35 {
36 if (n == 0 && k == 0)
37 break;
38 init(n, c1, c2);
39 sort(c1 + 1, c1 + n + 1);
40 sort(c2 + 1, c2 + n);
41 memset(dp1, 0, sizeof(dp1));
42 memset(dp2, 0, sizeof(dp2));
43 bishops(n, dp1, c1);
44 bishops(n - 1, dp2, c2);
45 ans = 0;
46 for (int i = 0; i <= k; i++)
47 ans += dp1[n][i] * dp2[n-1][k-i];
48 printf("%d\n", ans);
49 }
50
51 return 0;
52 }
注：本文作于2009年6月23日 19点51分