TYVJ 2002 扑克牌题解

P2002 扑克牌

时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

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

输入

输出

备注

对于100%的数据，0<=A,B,C,D<=15

lydrainbowcat - "Admin生日"杯NOIP模拟赛第三题

————————————————————我是分割线————————————————————————

好题。

数学期望DP
用记忆化搜索实现。

数组竟然六维，可怕......

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include<iomanip>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 double dp[][][][][][];

 bool vis[][][][][][];

 int t[];

 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==)+(f==))>=t[])&&((b+(e==)+(f==))>=t[])&&((c+(e==)+(f==))>=t[])&&((d+(e==)+(f==))>=t[])) return dp[a][b][c][d][e][f]=0.0;

     int sum=a+b+c+d+(e!=)+(f!=);

     double F=;

     if (a<) F+=dfs(a+,b,c,d,e,f)*(-a)/(-sum);

     if (b<) F+=dfs(a,b+,c,d,e,f)*(-b)/(-sum);

     if (c<) F+=dfs(a,b,c+,d,e,f)*(-c)/(-sum);

     if (d<) F+=dfs(a,b,c,d+,e,f)*(-d)/(-sum);

     double md=; if (e==) {for (int i=;i<;++i) md=min(dfs(a,b,c,d,i,f)/(-sum),md); F+=md;}

            md=; if (f==) {for (int i=;i<;++i) md=min(dfs(a,b,c,d,e,i)/(-sum),md); F+=md;}

     vis[a][b][c][d][e][f]=true;

     return dp[a][b][c][d][e][f]=F;

 }

 int main()

 {

     memset(vis,false,sizeof vis);

     int a,b,c,d;

     scanf("%d%d%d%d",&t[],&t[],&t[],&t[]);

     a=t[];b=t[];c=t[];d=t[];

     double ans=dfs(,,,,,);

     if (ans>54.0) printf("-1.000\n");

     else cout<<setiosflags(ios::fixed)<<setprecision()<<ans;

 }

tyvj 2002

扑克