随笔 - 68  文章 - 57  trackbacks - 0
<2010年2月>
31123456
78910111213
14151617181920
21222324252627
28123456
78910111213

常用链接

留言簿(8)

随笔分类(74)

随笔档案(68)

搜索

  •  

最新评论

阅读排行榜

评论排行榜

【题目大意】
  给定一个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, 0sizeof(int* N);
 9     memset(c2, 0sizeof(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, 0sizeof(dp1));
42         memset(dp2, 0sizeof(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分

posted on 2010-02-06 17:58 sdfond 阅读(2207) 评论(2)  编辑 收藏 引用 所属分类: Algorithm - Dynamic ProgrammingAlgorithm - Combinatorics

FeedBack:
# re: UVa 861 Little Bishops 2010-03-07 16:53 starvae
谢谢小甘露~  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理