1419: Red is good

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 639  Solved: 247

[][][]

Description

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

Input

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

Output

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

Sample Input

5 1

Sample Output

4.166666

HINT

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

Source

题解：sb出题人，把内存开那么小，强行一波动态数组！

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define maxn 5010#define mod 1000000int n,m,ans;double f[2][maxn];int main(){    scanf("%d%d",&n,&m);    int now=0;    for (int i=1;i<=n;i++,now=1-now){        f[now][0]=i;        for (int j=1;j<=m;j++)            f[now][j]=max(0.0,(f[now^1][j]+1)*i/(i+j)+(f[now][j-1]-1)*j/(i+j));    }    long long ans=floor(f[now^1][m]*mod);    printf("%lld.%06lld",ans/mod,ans%mod);    return 0;}