UVa 1637 纸牌游戏（全概率公式）

https://vjudge.net/problem/UVA-1637

题意：

36张牌分成9堆，每堆4张牌。每次可以拿走某两堆顶部的牌，但需要点数相同。每种拿法的概率均为1/5。求成功概率。

思路：

可以用9元组来表示当前状态，d[i]表示状态i对应的成功概率。

根据全概率公式：一个状态的成功率，等于其后继状态的成功率的平均值。

看到别人用vector来简洁的表示了状态，值得学习。

vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t （相当于数组，但是如果要比较状态的话就会比较方便）

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<queue>
 7 #include<cmath>
 8 #include<map>
 9 using namespace std;
10 
11 char card[9][4][3];
12 map<vector<int>,double> d;
13 
14 bool read()
15 {
16     for(int i=0;i<9;i++)
17     for(int j=0;j<4;j++)
18     if(scanf("%s",card[i][j])!=1) return false;
19     return true;
20 }
21 
22 double dp(vector<int> p,int num)
23 {
24     if(num==0)  return 1;    //全部取完
25     if(d.count(p)!=0)  return d[p];  //记忆化
26     int tot=0;
27     double sum=0;
28     for(int i=0;i<9;i++)
29     {
30         if(p[i])
31         for(int j=i+1;j<9;j++)
32         {
33             if(p[j])
34             if(card[i][p[i]-1][0]==card[j][p[j]-1][0])
35             {
36                 tot++;
37                 p[i]--;p[j]--;
38                 sum+=dp(p,num-2);
39                 p[i]++;p[j]++;
40             }
41         }
42     }
43     if(tot==0)  return d[p]=0;
44     else return d[p]=sum/tot;
45 }
46 
47 int main()
48 {
49     //freopen("D:\input.txt","r",stdin);
50     while(read())
51     {
52         vector<int> p(9,4);  
53         d.clear();
54         printf("%.6f
",dp(p,36));
55     }
56     return 0;
57 }