首页 > 代码库 > UVa 1637 (概率) Double Patience
UVa 1637 (概率) Double Patience
题意：
一共有9堆牌，每堆牌四张。每次可以取堆顶点数相同的两张牌，如果有多种方案则选取是随机的。
如果最后将所有牌取完，则视为游戏胜利，求胜利的概率。
分析：
用一个九元组表示状态，分别代表每堆牌剩余的牌数。根据全概率公式，d[i]为后继状态成功概率的平均值。
1 #include <iostream> 2 #include <cstdio> 3 #include <map> 4 #include <vector> 5 using namespace std; 6 7 map<vector<int>, double> d; 8 char card[9][4][3]; 9 10 double dp(vector<int>& cnt, int c)11 {12 if(c == 0) return 1; //所有的牌取完，游戏胜利概率为113 if(d.count(cnt) != 0) return d[cnt];14 double sum = 0; //后继状态的总概率15 int tot = 0; //后继状态的数量16 for(int i = 0; i < 9; ++i) if(cnt[i] > 0)17 for(int j = i + 1; j < 9; ++j) if(cnt[j] > 0)18 if(card[i][cnt[i]-1][0] == card[j][cnt[j]-1][0])19 {20 tot++;21 cnt[i]--, cnt[j]--;22 sum += dp(cnt, c-2);23 cnt[i]++, cnt[j]++;24 }25 if(tot == 0) return d[cnt] = 0;26 return d[cnt] = sum / tot;27 }28 29 bool read()30 {31 for(int i = 0; i < 9; ++i)32 for(int j = 0; j < 4; ++j)33 if(scanf("%s", card[i][j]) != 1)34 return false;35 return true;36 }37 38 int main()39 {40 //freopen("in.txt", "r", stdin);41 while(read())42 {43 vector<int> cnt(9, 4);44 d.clear();45 printf("%.6f\n", dp(cnt, 36));46 }47 48 return 0;49 }
UVa 1637 (概率) Double Patience
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。