TYVJ P2002 扑克牌

背景

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模拟赛 第三题
Blog: www.lydrainbowcat.tk  Email: [email protected]

决策挺复杂的。

现在不想写解析，日后补。

 /*by SilverN*/

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int mxn=;

 double f[mxn][mxn][mxn][mxn][][];

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

 int x1,x2,x3,x4;

 double dp(int a,int b,int c,int d,int e,int g){

     if(vis[a][b][c][d][e][g])return f[a][b][c][d][e][g];

     int i;

     if(((a+(e==)+(g==))>=x1) && ((b+(e==)+(g==))>=x2) && ((c+(e==)+(g==))>=x3) && ((d+(e==)+(g==))>=x4))

         return f[a][b][c][d][e][g]=;

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

     double tmp=;

     //普通

     if(a<)tmp+=dp(a+,b,c,d,e,g)*(-a)/(-sum);

     if(b<)tmp+=dp(a,b+,c,d,e,g)*(-b)/(-sum);

     if(c<)tmp+=dp(a,b,c+,d,e,g)*(-c)/(-sum);

     if(d<)tmp+=dp(a,b,c,d+,e,g)*(-d)/(-sum);

     //王

     double es;

     if(e==){

         es=;

         for(i=;i<=;i++) es=min(dp(a,b,c,d,i,g)/(-sum),es);

         tmp+=es;

     }

     if(g==){

         es=;

         for(i=;i<=;i++) es=min(dp(a,b,c,d,e,i)/(-sum),es);

         tmp+=es;

     }

     vis[a][b][c][d][e][g]=;

     return f[a][b][c][d][e][g]=tmp;

 }

 int main(){

     memset(vis,,sizeof(vis));

     int a,b,c,d;

     scanf("%d%d%d%d",&x1,&x2,&x3,&x4);

     double ans=dp(,,,,,);

     if(ans>)ans=-;

     printf("%.3lf\n",ans);

     return ;

 }