扑克牌

CH

题意:有一副扑克(54张牌(包括大王小王))，随机从中抽牌不放回，问得到A张黑桃、B张红桃、C张梅花、D张方块所需抽牌的牌数的期望数，大王和小王可以作为任意一种花色的牌对待，求最小期望，(0<=A,B,C,D<=15)

分析:设(f[i][j][l][r][x][y])表示当前已经翻了i张黑桃,j张红桃,l张梅花,r张方块,小王状态为x,大王状态为y(x=0,1,2,3,4分别表示没抽到,黑桃,红桃,梅花,方块,y同理):

所以初始化(f[A][B][C][D][?][?]=0),目标(f[0][0][0][0][0][0])

当前剩下的牌为(rest=54-(a+b+c+d+(x!=0)+(y!=0)))张:

以黑桃为例,(f[i][j][l][r][x][y]+=(13-i)/rest*f[i+1][j][l][r][x][y]),其余三种花色同理累加进去就可以了.

以小王为例,当x=0时,(f[i][j][l][r][x][y]+=1/rest*min_{1<=xx<=4}f[i][j][l][r][xx][y]),大王同理累加进去就可以了.

记忆化搜索实现.

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
   return s*w;
}
int A,B,C,D;double f[15][15][15][15][5][5];
inline bool check(int a,int b,int c,int d,int x,int y){
    if(x==1)a++;else if(x==2)b++;else if(x==3)c++;else if(x==4)d++;
    if(y==1)a++;else if(y==2)b++;else if(y==3)c++;else if(y==4)d++;
    if(a>=A&&b>=B&&c>=C&&d>=D)return true;else return false;
}
inline double dfs(int a,int b,int c,int d,int x,int y){
    double &ans=f[a][b][c][d][x][y];
    if(ans)return f[a][b][c][d][x][y];
    if(check(a,b,c,d,x,y))return 0;
    int rest=54-(a+b+c+d+(x>0)+(y>0));
    if(a<13)ans+=dfs(a+1,b,c,d,x,y)*(13-a)/rest;
    if(b<13)ans+=dfs(a,b+1,c,d,x,y)*(13-b)/rest;
    if(c<13)ans+=dfs(a,b,c+1,d,x,y)*(13-c)/rest;
    if(d<13)ans+=dfs(a,b,c,d+1,x,y)*(13-d)/rest;
    if(!x)ans+=min(min(dfs(a,b,c,d,1,y),dfs(a,b,c,d,2,y)),min(dfs(a,b,c,d,3,y),dfs(a,b,c,d,4,y)))/rest;
    if(!y)ans+=min(min(dfs(a,b,c,d,x,1),dfs(a,b,c,d,x,2)),min(dfs(a,b,c,d,x,3),dfs(a,b,c,d,x,4)))/rest;
    return ++ans;
}
int main(){
    A=read(),B=read(),C=read(),D=read();int bj=0;
    if(A>13)bj+=A-13;if(B>13)bj+=B-13;if(C>13)bj+=C-13;if(D>13)bj+=D-13;
    if(bj>2)puts("-1.000");
    else printf("%.3lf
",dfs(0,0,0,0,0,0));
    return 0;
}