首页 > 代码库 > cf 148D Bag of mice

cf 148D Bag of mice

The dragon 选一只老鼠,然后会跑掉一只

the princess选一只老鼠,不会跑出另外的老鼠

求the princess赢的概率

 1 #include<iostream> 2 #include<string> 3 #include<cstdio> 4 #include<vector> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<cstring> 9 #include<stdlib.h>10 #include<cmath>11 using namespace std;12 #define pb push_back13 double dp[1010][1010];14 int main(){15     int w,b;16     while(cin>>w>>b){17         memset(dp,0,sizeof(dp));18         dp[1][0]=1;19         for(int i=1;i<=w;i++)20         for(int j=0;j<=b;j++){21             double p1,p2;22             int a=i,b=j;23             dp[i][j]=1.0*i/(i+j);24             if(b>=1){25                 p1=1.0*b/(a+b);26                 b--; //the princess选了一只27                 if(b>=1){28                     p2=1.0*b/(a+b);//The dragon 选一只29                     b--;30                     if(b>=1)31                         dp[i][j]+=p1*p2*b/(a+b)*dp[i][j-3];32                     dp[i][j]+=p1*p2*a/(a+b)*dp[i-1][j-2];33                 }34             }35         }36         printf("%.10lf\n",dp[w][b]);37     }38 }