【題目大意】
給定一個(gè)n*n的棋盤，求放置k個(gè)互不攻擊的象的方法數(shù)。其中n <= 8，k <= n ^
2。
【題目分析】
對(duì)于棋盤放車問題可以用組合數(shù)學(xué)的知識(shí)來(lái)解決，但是對(duì)于含禁區(qū)的擺放問題，雖然組合數(shù)學(xué)給出了經(jīng)典的棋盤多項(xiàng)式+容斥原理的解法，但是實(shí)際中棋盤多項(xiàng)式的求解是很困難的，因此一般需要借助狀態(tài)壓縮動(dòng)態(tài)規(guī)劃求解。
現(xiàn)在題目中要求出互不攻擊的象的方法數(shù)，象的攻擊路線是斜的，是不是可以考慮采用放車的方法來(lái)解呢？將棋盤黑白染色，如果一個(gè)象在黑色的格子里面，那么它一定不會(huì)攻擊到白色的格子，這樣的話可以分開計(jì)數(shù)，然后最后利用乘法原理加起來(lái)就行了。把棋盤旋轉(zhuǎn)45度，這樣象的攻擊路線就是直的了，如果只考慮一種顏色的話，那么問題就轉(zhuǎn)變成了經(jīng)典的放車問題了，可以利用動(dòng)態(tài)規(guī)劃解決。
設(shè)dp[i][j]表示前i行放了j個(gè)車的方法數(shù)，c[i]表示第i行可以放置的棋子數(shù)量，那么轉(zhuǎn)移方程為：
dp[i][j]
= dp[i-1][j] + dp[i-1][j-1] * (c[i] - (j -
1))
需要注意的是c數(shù)組應(yīng)該是增序的，這樣才能保證前面的j-1行放了車，對(duì)應(yīng)這一行就有j-1個(gè)位置不可放了。
這個(gè)題目的dp方程不難想，但是如何把模型轉(zhuǎn)化到放車問題是不容易想到的，尤其是將棋盤黑白染色后分開計(jì)數(shù)的想法，非常巧妙。
題目代碼：
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點(diǎn)51分