邱老师看电影

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

Sample Input	Sample Output
1 3	0.500000000

Source

2015 UESTC Training for Dynamic Programming

#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   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]四种特殊情况

转载于:https://www.cnblogs.com/smilesundream/p/5767497.html

你可能感兴趣的文章