题目大意：36张牌分成9堆，每堆4张牌。每次可以拿走某两堆顶部的牌，但需要点数相同。如果有多种拿法则等概率的随机拿。例如9对顶部的牌分别为KS,KH,KD,9H,8S,8D,7C,7D,6H,则有5种拿法(KS,KH),(KS,KD),(KH,KD),(8S,8D),(7C,7D),每种拿法的概率为1/5。如果最后拿完所有牌则游戏成功。按顺序给出每堆牌的4张牌，求成功概率。
题目分析：（手动%aufeas。 用一个九维的数组f来表示这九堆剩余牌数时的概率大小。用记忆化搜索实现。每次枚举当前牌堆顶的牌，如果点数相等就累计一下。最后把这两张牌成功时的方案数/刚刚累计的方案数就是概率大小。累加起来。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> #include<cmath> #include<cctype> #include<cassert> #include<climits> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define ForD(i,n) for(int i=n;i;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define RepD(i,n) for(int i=n;i>=0;i--) #define MEM(a) memset(a,0,sizeof(a)) #define MEMI(a) memset(a,127,sizeof(a)) #define MEMi(a) memset(a,128,sizeof(a)) #define INF (2139062143) #define phiF (1000000006) #define MAXN (1000000+10) typedef long long LL; double b[5][5][5][5][5][5][5][5][5],ans; int a[10]; char c[10][5],s[5]; bool f[5][5][5][5][5][5][5][5][5]; double dfs(){ double ans=0.0; int t=0,num=0,use[20]; if (f[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]]) { return b[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]]; } f[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]]=1; Rep (i,9) if (a[i]) use[++t]=i; if (!t) return b[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]]=1.0; For (i,t-1) Fork (j,i+1,t) if (c[use[i]][a[use[i]]]==c[use[j]][a[use[j]]]) num++; For (i,t-1) Fork (j,i+1,t) if (c[use[i]][a[use[i]]]==c[use[j]][a[use[j]]]) { a[use[i]]--;a[use[j]]--; ans+=dfs()/1.0/num; a[use[i]]++;a[use[j]]++; } return b[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]]=ans; } int main(){ Rep (i,9){ For (j,4){ scanf("%s",s); c[i][j]=s[0]; } scanf("\n"); } Rep (i,9)a[i]=4; printf("%.10f",(double)dfs()); }
