邱老师看电影

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status

一天邱老师心血来潮想去看电影，但是邱老师的妹子想去逛街，他们谁也没有办法说服对方，于是准备来玩一个游戏来决定听谁的。

邱老师找来w只白鼠和b只黑鼠，邱老师和妹子轮流从袋子里面抓老鼠，谁先抓到白色老鼠谁就赢。

但是有酱神在旁边捣乱，邱老师每抓一只老鼠出来，酱神就偷偷的也从里面抓一只出来，这3个人抓出来的老鼠都是随机的。

如果袋子里没有白老鼠，且之前没有人拿到白老鼠的时候，邱老师胜。

为了体现绅士精神，邱老师让妹子先抓，那么妹子赢的概率是多少呐？

Input

只有两个数字 w和b w<=1000 b<=1000

Output

输出妹子赢的概率保留9位小数

Sample input and output

1 3	0.500000000

Source

2015 UESTC Training for Dynamic Programming

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int  inf =0x7f7f7f7f;

const double pi=acos(-1);

const int N=1005;

double dp[N][N];

int main()

{

     for(int i=1;i<=1000;i++) {dp[0][i]=0;dp[i][0]=1;}

     for(int i=1;i<=1000;i++)

     {

         double ix=i;

         dp[i][1]=ix/(ix+1);

     }

     dp[1][2]=1.0/3;

     for(int i=2;i<=1000;i++)

     {

         double ix=i;

         dp[i][2]=ix/(ix+2)+2/(ix+2)*1/(ix+1);

     }

     for(int w=1;w<=1000;w++)

        for(int b=3;b<=1000;b++)

         {

             double w1=w,b1=b;

             dp[w][b]=w1/(w1+b1)+

                      b1/(w1+b1)*(b1-1)/(w1+b1-1)*

                      (w1/(w1+b1-2)*dp[w-1][b-2]+(b1-2)/(w1+b1-2)*dp[w][b-3]);

         }

     int w,b;

     while(~scanf("%d%d",&w,&b))

         printf("%.9f\n",dp[w][b]);

     return 0;

}

　　概率递推公式：

 dp[w][b]=w1/(w1+b1)+

 b1/(w1+b1)*(b1-1)/(w1+b1-1)*

 (w1/(w1+b1-2)*dp[w-1][b-2]+(b1-2)/(w1+b1-2)*dp[w][b-3]);
所以需要预处理出  dp[0][i],dp[i][0],dp[i][1],dp[i][2]四种特殊情况

邱老师