首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。