扑克牌 概率dp
题意:
从54张牌中抽牌,问抽到a张红,b张黑,c张方,d张梅的概率,当抽取到大王和小王的时候,会固定抽期望步数最少的牌。求最小的期望步数。
思路:期望dp ,dp(a,b,c,d,e,f),a,b,c,d,代表前4种牌的数量,e,f代表大王和小王的状态,要注意判断不合法的情况,即所有牌都抽完了,还是没有得到想要的局面。然后我做的时候理解错题意了,把题意理解炒成期望步数了,其实抽到小王大王的时候选择是固定的,而没有四个分支。
#include<bits/stdc++.h>
using namespace std;
const double inf=1e20;
double dp[16][16][16][16][5][5];
// 54张牌:13张方块 13张梅花 13张 黑桃 13张红桃 1张大王 一张小王
int A,B,C,D;
double dfs(int a,int b,int c,int d,int sk,int bk)
{
if(dp[a][b][c][d][sk][bk]>=0) return dp[a][b][c][d][sk][bk];
int aa=a+(sk==0)+(bk==0);
int bb=b+(sk==1)+(bk==1);
int cc=c+(sk==2)+(bk==2);
int dd=d+(sk==3)+(bk==3);
if(aa>=A && bb>=B && cc>=C && dd>=D) return dp[a][b][c][d][sk][bk]=0;
if((a+b+c+d+(sk!=4)+(bk!=4))==54) return dp[a][b][c][d][sk][bk]=inf;
int al=54-(a+b+c+d+(sk!=4)+(bk!=4));
double res=0;
if(a+1<=13)
res+=((13-a)*1.0/al *(1+dfs(a+1,b,c,d,sk,bk)));
if(b+1<=13)
res+=((13-b)*1.0/al*(1+dfs(a,b+1,c,d,sk,bk)));
if(c+1<=13)
res+=((13-c)*1.0/al*(1+dfs(a,b,c+1,d,sk,bk)));
if(d+1<=13)
res+=((13-d)*1.0/al*(1+dfs(a,b,c,d+1,sk,bk)));
if(sk==4)
{
double tt=inf;
for(int i=0;i<=3;i++)
tt=min(tt,dfs(a,b,c,d,i,bk));
res+=1.0/al*(1+tt);
}
if(bk==4)
{
double tt=inf;
for(int i=0;i<=3;i++)
tt=min(tt,dfs(a,b,c,d,sk,i));
res+=1.0/al*(1+tt);
}
return dp[a][b][c][d][sk][bk]=res;
}
int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
A=a,B=b,C=c,D=d;
memset(dp,-1,sizeof dp);
double tt=dfs(0,0,0,0,4,4);
if(tt>inf/2) cout<<"-1.000"<<endl;
else
printf("%.3lf\n",tt);
}