问题 J: Red is good

时间限制: 1 Sec 内存限制: 64 MB

提交: 15 解决: 7

题目描述

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

输入

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

输出

在最优策略下平均能得到多少钱。

样例输入

5 1

样例输出

4.166666

提示

输出答案时,小数点后第六位后的全部去掉,不要四舍五入.

状态转移挺有意思的，f[i][j]表示牌堆初始有i张红牌，j张黑牌，那么转移：如果第一次抽到红牌，那么概率为i/(i+j)，抽完这张红牌后还剩下i-1张红牌，j张黑牌，那不就是f[i-1][j]了么。第一次抽到黑牌以此类推。

f[i][0]=i;

f[i][j]=max(0,(f[i-1][j]+1)*i/(i+j)+(f[i][j-1]-1)*j/(i+j));

不四舍五入还是挺简单的，用int卡一下即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;double f[3][5005];int n,m;int main(){    cin>>n>>m;    for(int i=0;i<=n;i++)    {       int k=i%2;f[k][0]=i;       for(int j=1;j<=m;j++)         f[k][j]=max(0.0,(f[k][j-1]-1.0)*(double)j/(i+j)+(f[k^1][j]+1.0)*(double)i/(i+j));    }    int ans=f[n%2][m]*1000000;    printf("%.6lf",(double)ans/1000000);}