首页 > 其他 > 详细

Red is good

时间:2017-08-24 16:05:35      阅读:215      评论:0      收藏:0      [点我收藏+]

题目描述

桌面上有R张红牌和B张黑牌,随机打乱顺序后放在桌面上,开始一张一张地翻牌,翻到红牌得到1美元,黑牌则付出1美元。可以随时停止翻牌,在最优策略下平均能得到多少钱。

输入

一行输入两个数R,B,其值在0到5000之间

输出

在最优策略下平均能得到多少钱。
solution
f[i][j]表示当前拿i个红球,j个黑球时的期望钱数
f[i][j]=max(0,( f[i-1][j]+1)*(i/(j+i)) + (f[i][j-1]-1)*(j/(i+j)) )
f[i][0]=i
由于内存,开滚动数组
技术分享
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #define dd double
 5 using namespace std;
 6 
 7 int R,B,now;
 8 dd f[2][5066];
 9 
10 int main(){
11     
12     scanf("%d%d",&R,&B);
13     
14     now=0;
15     dd temp;
16     for(int i=1;i<=R;++i)
17     {
18         now^=1;
19         f[now][0]=i;
20         for(int j=1;j<=B;++j)
21         {
22             temp=(f[now][j-1]-1)*(dd)(j)/(dd)(i+j)+(f[now^1][j]+1)*(dd)(i)/(dd)(i+j);
23           f[now][j]=temp>0?temp:0;
24         }
25     }
26     printf("%.6lf",f[now][B]-0.0000005);
27     
28     //while(1);
29 }
code

Red is good

原文:http://www.cnblogs.com/A-LEAF/p/7423442.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!