说句实话,假如不认真再想想期望就是平均数,你会对期望很迷惑.
因为dfs是从后往前的,我们要求的答案是dp[0][0][0][0][4][4]当成答案,我们考虑用后面状态来更新前面状态.
对于普通的4种花色来说,假设我们现在的状态是dp[a][b][c][d][x][y].
那么我们从什么转移到它呢?
显然有四种:
我们令cnt=a+b+c+d+(x!=4)+(y!=4). dp[a+1][b][c][d][x][y]<-它(这样转移的概率是从最后的部分选a的概率(13-a)/(54-cnt)) dp[a][b+1][c][d][x][y]<-它(这样转移的概率是从最后的部分选b的概率(13-b)/(54-cnt)) dp[a][b][c+1][d][x][y]<-它(这样转移的概率是从最后的部分选c的概率(13-c)/(54-cnt)) dp[a][b][c][d+1][x][y]<-它(这样转移的概率是从最后的部分选d的概率(13-d)/(54-cnt))
dfs是反的ε=(´ο`*)))唉.
它自己为1.0...
然后考虑鬼.1/(54-cnt).然后显然我们要拿最小的转移给它.
emm,没了.
代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N=16;
double dp[N][N][N][N][5][5];
int st[N][N][N][N][5][5];
int A,B,C,D;
double get_ans(int a,int b,int c,int d,int x,int y)
{
if(st[a][b][c][d][x][y]) return dp[a][b][c][d][x][y];
if(a+(x==0)+(y==0)>=A&&b+(x==1)+(y==1)>=B&&c+(x==2)+(y==2)>=C&&d+(x==3)+(y==3)>=D) return 0;//假如都选了那么肯定为0.
st[a][b][c][d][x][y]=1;
double sum=1.0;
int cnt=a+b+c+d+(x!=4)+(y!=4);
if(a<13) sum+=get_ans(a+1,b,c,d,x,y)*(13-a)/(54-cnt);
if(b<13) sum+=get_ans(a,b+1,c,d,x,y)*(13-b)/(54-cnt);
if(c<13) sum+=get_ans(a,b,c+1,d,x,y)*(13-c)/(54-cnt);
if(d<13) sum+=get_ans(a,b,c,d+1,x,y)*(13-d)/(54-cnt);
if(x==4)
{
double mi=312312.0;
for(int i=0;i<4;i++)
{
mi=min(mi,get_ans(a,b,c,d,i,y)/(54-cnt));
}
sum+=mi;
}
if(y==4)
{
double mi=312312.0;
for(int i=0;i<4;i++)
{
mi=min(mi,get_ans(a,b,c,d,x,i)/(54-cnt));
}
sum+=mi;
}
return dp[a][b][c][d][x][y]=sum;
}
int main()
{
cin>>A>>B>>C>>D;
get_ans(0,0,0,0,4,4);
if(max(A-13,0)+max(B-13,0)+max(C-13,0)+max(D-13,0)>2)
{
printf("-1.000\n");
}
else printf("%.3lf\n",dp[0][0][0][0][4][4]);
return 0;
}
京公网安备 11010502036488号