一共9堆牌，每堆牌有0~4 这5种状态，所以一共有5^9=1953125种
状态定义：对于状态i，d[i]表示在这种状态下要成功的概率，也即是后序状态成功几率的平均值(因为每种状态选取的几率一样)
状态转移：也即是1)拿这两对相同的牌 2)拿下一对相同的牌
状态选取：因为是计算总的成功的概率所以不存在最优的解
概率计算：利用全概率公式，也即是 一个状态的成功的概率 等于 后续状态下的成功概率平均值之和
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
char card[9][4][3];
map<vector<int>,double> d;
bool readcard()
{for(int i=0;i<9;i++)for(int j=0;j<4;j++)if(scanf("%s",card[i][j])!=1) return false;return true;
}
double dp(vector<int>& cnt,int c) //返回的是cnt这种状态下成功的几率
{if(c==0) return 1; //已经成功了 if(d.count(cnt)!=0) return d[cnt]; //表明此状态已经计算过了(记忆化搜索) int tot=0; //记录决策数 double sum=0; for(int i=0;i<9;i++) if(cnt[i]) //第i堆牌的数量>0 for(int j=i+1;j<9;j++) if(cnt[j]) //第i堆牌的数量>0if(card[i][cnt[i]-1][0]==card[j][cnt[j]-1][0]) 第i堆牌的第一张和第j堆牌的第一张一样 {tot++;cnt[i]--;cnt[j]--;sum+=dp(cnt,c-2); //sum计算所有此状态下成功的概率 cnt[i]++;cnt[j]++;}if(!tot) return d[cnt]=0; //这种状态下不可能成功 else return d[cnt]=sum/tot ; //这种状态下成功的几率均分为tot份
}
int main()
{while(readcard()){vector<int> cnt(9,4); //表示状态;d.clear();printf("%.6lf\n",dp(cnt,36)); }return 0;
}