NC51071. 扑克牌
描述
Admin生日那天，Rainbow来找Admin玩扑克牌……
玩着玩着Rainbow觉得太没意思了,于是决定给Admin一个考验~~~
Rainbow把一副扑克牌(54张)随机洗开，倒扣着放成一摞。然后Admin从上往下依次翻开每张牌，每翻开一张黑桃、红桃、梅花或者方块，就把它放到对应花色的堆里去。
Rainbow想问问Admin，得到A张黑桃、B张红桃、C张梅花、D张方块需要翻开的牌的张数的期望值E是多少？
特殊地，如果翻开的牌是大王或者小王，Admin将会把它作为某种花色的牌放入对应堆中,使得放入之后E的值尽可能小。
由于Admin和Rainbow还在玩扑克，所以这个程序就交给你来写了~
输入描述
输入仅由一行，包含四个用空格隔开的整数，A,B,C,D。
输出描述
输出需要翻开的牌数的期望值E，四舍五入保留3位小数。
如果不可能达到输入的状态，输出-1.000。
示例1
输入:
1 2 3 4
输出:
16.393
示例2
输入:
15 15 15 15
输出:
-1.000
C++(g++ 7.5.0) 解法, 执行用时: 53ms, 内存消耗: 10240K, 提交时间: 2022-08-05 11:43:14
#include<bits/stdc++.h>
using namespace std;
double dp[15][15][15][15][5][5];
bool vis[15][15][15][15][5][5];
int A,B,C,D;
double dfs(int a,int b,int c,int d,int e,int f)
{
if(vis[a][b][c][d][e][f]) return dp[a][b][c][d][e][f];
if((a+(e==0)+(f==0)>=A)&&(b+(e==1)+(f==1)>=B)&&(c+(e==2)+(f==2)>=C)&&(d+(e==3)+(f==3)>=D))
return 0.0;
double ret=1.0;
int sum=a+b+c+d+(e!=4)+(f!=4);
if(a<13) ret+=dfs(a+1,b,c,d,e,f)*(13-a)/(54-sum);
if(b<13) ret+=dfs(a,b+1,c,d,e,f)*(13-b)/(54-sum);
if(c<13) ret+=dfs(a,b,c+1,d,e,f)*(13-c)/(54-sum);
if(d<13) ret+=dfs(a,b,c,d+1,e,f)*(13-d)/(54-sum);
if(e==4) ret+=min({dfs(a,b,c,d,0,f),dfs(a,b,c,d,1,f),dfs(a,b,c,d,2,f),dfs(a,b,c,d,3,f)})/(54-sum);
if(f==4) ret+=min({dfs(a,b,c,d,e,0),dfs(a,b,c,d,e,1),dfs(a,b,c,d,e,2),dfs(a,b,c,d,e,3)})/(54-sum);
vis[a][b][c][d][e][f]=true;
return dp[a][b][c][d][e][f]=ret;
}
int main()
{
scanf("%d%d%d%d",&A,&B,&C,&D);
double ans=dfs(0,0,0,0,4,4);
if(ans>54) puts("-1.000");
else printf("%.3f\n",ans);
}
C++11(clang++ 3.9) 解法, 执行用时: 77ms, 内存消耗: 13576K, 提交时间: 2020-08-30 18:13:08
#include<bits/stdc++.h>
using namespace std;
double s[20][20][20][20][5][5]={false};
bool bk[20][20][20][20][5][5];
int A,B,C,D;
double dfs(int a,int b,int c,int d,int e,int f){
if(bk[a][b][c][d][e][f]) return s[a][b][c][d][e][f];
if((a+(e==0)+(f==0)>=A)&&(b+(e==1)+(f==1)>=B)&&(c+(e==2)+(f==2)>=C)&&(d+(e==3)+(f==3)>=D)) return 0;
double rec=1.0;
bk[a][b][c][d][e][f]=true;
double sum=54-a-b-c-d-(e!=4)-(f!=4);
if(a<13) rec+=dfs(a+1,b,c,d,e,f)*(13-a)/sum;
if(b<13) rec+=dfs(a,b+1,c,d,e,f)*(13-b)/sum;
if(c<13) rec+=dfs(a,b,c+1,d,e,f)*(13-c)/sum;
if(d<13) rec+=dfs(a,b,c,d+1,e,f)*(13-d)/sum;
if(e==4){
double mi=1e9;
for(int i=0;i<4;i++){
mi=min(mi,dfs(a,b,c,d,i,f));
}
rec+=mi/sum;
}
if(f==4){
double mi=1e9;
for(int i=0;i<4;i++){
mi=min(mi,dfs(a,b,c,d,e,i));
}
rec+=mi/sum;
}
return s[a][b][c][d][e][f]=rec;
}
int main(){
scanf("%d%d%d%d",&A,&B,&C,&D);
double ans=dfs(0,0,0,0,4,4);
if(ans>54) puts("-1.000");
else printf("%.3lf\n",ans);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 62ms, 内存消耗: 13792K, 提交时间: 2020-03-26 15:45:38
#include<bits/stdc++.h>
using namespace std;
double s[20][20][20][20][5][5];
bool bk[20][20][20][20][5][5];int A,B,C,D;
double dfs(int a,int b,int c,int d,int e,int f)
{
if(bk[a][b][c][d][e][f]) return s[a][b][c][d][e][f];
if((a+(e==0)+(f==0))>=A&&(b+(e==1)+(f==1))>=B&&(c+(e==2)+(f==2))>=C
&&(d+(e==3)+(f==3))>=D) return 0;
bk[a][b][c][d][e][f]=true;
double rec=1.0,sum=54-a-b-c-d-(e!=4)-(f!=4);
if(a<13) rec+=dfs(a+1,b,c,d,e,f)*(13-a)/sum;
if(b<13) rec+=dfs(a,b+1,c,d,e,f)*(13-b)/sum;
if(c<13) rec+=dfs(a,b,c+1,d,e,f)*(13-c)/sum;
if(d<13) rec+=dfs(a,b,c,d+1,e,f)*(13-d)/sum;
if(e==4){
double mi=1e9;
for(int i=0;i<4;i++)
mi=min(mi,dfs(a,b,c,d,i,f));
rec+=mi/sum;
}
if(f==4){
double mi=1e9;
for(int i=0;i<4;i++)
mi=min(mi,dfs(a,b,c,d,e,i));
rec+=mi/sum;
}
return s[a][b][c][d][e][f]=rec;
}
int main()
{
scanf("%d%d%d%d",&A,&B,&C,&D);
double ans=dfs(0,0,0,0,4,4);
if(ans>54) printf("-1.000\n");
else printf("%.3lf\n",ans);
}