Posted on 2010-08-25 15:53
lzh525 阅读(1109)
评论(0) 编辑 收藏 引用 所属分类:
ＡＣＭ解题报告
【题目大意】
给定一个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个位 1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 const int N = 70;
5
6 void init(int n, int *c1, int *c2)//将棋盘分为黑白两个区域，使得相同颜色的才在象的攻击范围内
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)%2)//白色区域
15 c2[(i+j)/2]++;//第(i+j)/2斜行有几个白色格子
16 else//黑色区域
17 c1[(i+j)/2]++;//第(i+j)/2斜行有几个黑色格子
18 }
19 }
20 }
21
22 void bishops(int n, int dp[N][N], int c[N])//计算过程
23 {
24 int i,j;
25 for(i=0;i<=n;i++)
26 dp[i][0]=1;
27 for(i=1;i<=n;i++)
28 for(j=1;j<=c[i];j++)
29 dp[i][j] = dp[i-1][j]+dp[i-1][j-1]*(c[i]-j+1);
30 }
31
32 int main()
33 {
34 int n, k, c1[N], c2[N], dp1[N][N], dp2[N][N], ans,i;
35
36 while(cin>>n>>k)
37 {
38 if (n==0&&k == 0)
39 break;
40 init(n,c1,c2);
41 sort(c1+1,c1+n+1);
42 sort(c2+1,c2+n);
43 memset(dp1,0,sizeof(dp1));
44 memset(dp2,0,sizeof(dp2));
45 bishops(n,dp1,c1);
46 bishops(n-1,dp2,c2);
47 ans=0;
48 for(i=0;i<=k;i++)
49 ans+=dp1[n][i]*dp2[n-1][k-i];
50 cout<<ans<<endl;
51 }
52
53 return 0;
54 }