《算法竞赛进阶指南》0x38概率与期望 扑克牌
题目链接：https://www.acwing.com/problem/content/description/220/
给定一副牌，设随机变量X，为拥有四种花色的牌的数量分别为a,b,c,d的时候的牌的数量，求X的数学期望。
容易得知，在计算一个状态的数学期望时，它能到达的所有状态的数学期望一定是计算完毕的，这个模式有点像拓扑排序和递归，但是拓扑排序过于复杂，所以考虑记忆化搜索。
每种状态到最终状态的期望等于它可达的点的数学期望加上边长（代价就是1，因为需要拿一张牌才能转移到下一个状态）再乘以这个状态转移的概率。根据公式化简后只需要设置初始期望是1.0再累加其余情况的期望即可，此时如果牌数用完了期望就是无穷大，即不可达，如果到达了目标状态，无需转移，不用花费代价，故期望是0。
代码：
#include<iostream> #include<cstdio> using namespace std; double dp[15][15][15][15][5][5]; bool vis[15][15][15][15][5][5]; const double inf=1e10; int A,B,C,D; double dfs(int a,int b,int c,int d,int x,int y){//记忆化搜索 if(vis[a][b][c][d][x][y])return dp[a][b][c][d][x][y]; vis[a][b][c][d][x][y]=1; double ans=1.0;//下一张牌作为转移的平均代价 int a1=a,b1=b,c1=c,d1=d; if(x==1)a1++;if(x==2)b1++;if(x==3)c1++;if(x==4)d1++; if(y==1)a1++;if(y==2)b1++;if(y==3)c1++;if(y==4)d1++; if(a1>=A && b1>=B && c1>=C && d1>=D) return dp[a][b][c][d][x][y]=0;//最终状态的数学期望是0 int remain=54-a1-b1-c1-d1;//剩余的牌的数量 if(remain<=0) return dp[a][b][c][d][x][y]=inf;//所有的牌都用完了还是没能到达最终状态 if(a<13)ans+=dfs(a+1,b,c,d,x,y)*(13-a)/remain; if(b<13)ans+=dfs(a,b+1,c,d,x,y)*(13-b)/remain; if(c<13)ans+=dfs(a,b,c+1,d,x,y)*(13-c)/remain; if(d<13)ans+=dfs(a,b,c,d+1,x,y)*(13-d)/remain; //尝试把大王小王看做某种花色使得期望尽量小 if(x==0){ double tmp=dfs(a,b,c,d,1,y); tmp=min(tmp,dfs(a,b,c,d,2,y)); tmp=min(tmp,dfs(a,b,c,d,3,y)); tmp=min(tmp,dfs(a,b,c,d,4,y)); ans+=tmp/remain; } if(y==0){ double tmp=dfs(a,b,c,d,x,1); tmp=min(tmp,dfs(a,b,c,d,x,2)); tmp=min(tmp,dfs(a,b,c,d,x,3)); tmp=min(tmp,dfs(a,b,c,d,x,4)); ans+=tmp/remain; } return dp[a][b][c][d][x][y]=ans; } int main(){ cin>>A>>B>>C>>D; double ans = dfs(0,0,0,0,0,0);//从初始点开始，每张牌都没有用过 if(ans>60)puts("-1.000"); else printf("%.3lf ",ans); }