题意：
一共有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; //所有的牌取完，游戏胜利概率为1 13 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 ", dp(cnt, 36)); 46 } 47 48 return 0; 49 }