说句实话,假如不认真再想想期望就是平均数,你会对期望很迷惑.
因为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; }