首页 > 代码库 > HDU2947Bicycle Puzzle(组合原理)

HDU2947Bicycle Puzzle(组合原理)

题目大意:

你和朋友两人玩游戏,将一个图片均等切割成W* H块,打乱每一小块的位置。拼图游戏开始。每次,可以交换任意两块,记下交换的次数,图片还原游戏结束。得分为执行交换的次数。得分越小越好。

现在,给你W和H, 还有你朋友的得分S,问,你能够得到小于S分的概率。

解题思路:

首先,在考虑问题时,只和块数有关,所以,N = W * H, W和H可以无视之。

然后,用 P[N][K] 表示:图片被分割成 N 块,需要交换 K 次才能使图片还原 的情况数目。那么,我们再 加上一小块,也就是说,把图片分割成 N + 1 块。假如,新加入的第 N + 1 块 它就在正确的位置上,那么,使图片还原需要 K 次操作]; 假如,新加入的第 N + 1 块不在正确的位置上,那么,它必定和前面 N 块中的某一块交换了位置, 则要把图片还原,就需要 K + 1 次操作。

整理一下可以得到下面的递推式:

p[i][j] = p[i - 1][j] + p[i - 1][j - 1] * (i - 1)

 1 #include <iostream>
 2 using namespace std;
 3 __int64 p[21][21];
 4 __int64 gcd(__int64 a, __int64 b)
 5 {
 6     return b ? gcd(b, a % b) : a;
 7 }
 8 void init()
 9 {
10     int i, j;
11     for (i = 0; i <= 20; ++i)
12     {
13         p[i][0] = 1;
14         p[i][i] = 0;
15     }
16     for (i = 2; i <= 20; ++i)
17         for (j = 1; j < i; ++j)
18             p[i][j] = p[i - 1][j] + p[i - 1][j - 1] * (i - 1);
19 }
20 void solve(int s, int n)
21 {
22     __int64 sum = 0, total = 0 , g;
23     int i;
24     for (i = 0; i < s; ++i)
25         sum += p[n][i];
26     total = sum;
27     for ( ; i < n; ++i)
28         total += p[n][i];
29     g = gcd(sum, total);
30     sum /= g;
31     total /= g;
32     if (total == 1 && sum == 1)
33         printf("1\n");
34     else if (sum == 0)
35         printf("0\n");
36     else printf("%I64d/%I64d\n", sum, total);
37 }
38 int main()
39 {
40     init();
41     int tcase, w, h, n, s;
42     scanf("%d", &tcase);
43     while (tcase--)
44     {
45         scanf("%d%d%d", &w, &h, &s);
46         solve(s, w * h);
47     }
48     return 0;
49 }