题目链接:Expected Cards - LightOJ 1364 - Virtual Judge (ppsucxtt.cn)
题意:Taha 把一副扑克牌(54张)随机洗开,倒扣着放成一摞。然后从上往下依次翻开每张牌,每翻开一张黑桃、红桃、梅花或者方块,就把它放到对应花色的堆里去。Taha想知道得到 A 张黑桃、B 张红桃、C 张梅花、D 张方块需要翻开的牌的张数的期望值 E 是多少?特殊地,如果翻开的牌是大王或者小王,Taha 将会把它作为某种花色的牌放入对应堆中,使得放入之后 E 的值尽可能小。
我之前做过一道基本上一模一样的题目,那道题目是单组输入,而这道题目是多组输入,只要记得初始化数组就好,下面附上我之前写的那道题的博客地址:(59条消息) (ACW218)扑克牌(数学期望)_AC__dream的博客-CSDN博客
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int N=16;
double f[N][N][N][N][5][5];
int A,B,C,D;
double dp(int a,int b,int c,int d,int E,int F)
{
if(f[a][b][c][d][E][F]) return f[a][b][c][d][E][F];
int cnta=a+(E==1)+(F==1);
int cntb=b+(E==2)+(F==2);
int cntc=c+(E==3)+(F==3);
int cntd=d+(E==4)+(F==4);
if(cnta>=A&&cntb>=B&&cntc>=C&&cntd>=D) return 0;
double ans=1;
int cnt=cnta+cntb+cntc+cntd;
if(a<13) ans+=1.0*(13-a)/(54-cnt)*dp(a+1,b,c,d,E,F);
if(b<13) ans+=1.0*(13-b)/(54-cnt)*dp(a,b+1,c,d,E,F);
if(c<13) ans+=1.0*(13-c)/(54-cnt)*dp(a,b,c+1,d,E,F);
if(d<13) ans+=1.0*(13-d)/(54-cnt)*dp(a,b,c,d+1,E,F);
if(E==0)
{
double t=9999999999;
for(int i=1;i<=4;i++)
t=min(t,dp(a,b,c,d,i,F)/(54-cnt));
ans+=t;
}
if(F==0)
{
double t=9999999999;
for(int i=1;i<=4;i++)
t=min(t,dp(a,b,c,d,E,i)/(54-cnt));
ans+=t;
}
return f[a][b][c][d][E][F]=ans;
}
int main()
{
int T;
cin>>T;
for(int o=1;o<=T;o++)
{
int n;
cin>>A>>B>>C>>D;
int t=0;
memset(f,0,sizeof f);
if(A>13) t+=A-13;
if(B>13) t+=B-13;
if(C>13) t+=C-13;
if(D>13) t+=D-13;
if(t>2) printf("Case %d: -1\n",o);
else printf("Case %d: %.10lf\n",o,dp(0,0,0,0,0,0));
}
return 0;
}