CF D. Bag of mice(概率dp) - c++编程基础

TOP

CF D. Bag of mice(概率dp)

2015-07-20 17:45:09 来源: 作者: 【大中小】浏览:3次

Tags：Bag mice 概率

这里有w只白鼠和b只黑鼠，龙和王妃轮流从袋子里抓鼠，每次抓一只，抓到第一只白鼠的人获胜。当龙抓一只鼠时，袋子里会跑掉一只鼠，跑掉的鼠是等概率的。问王妃获胜的概率。

设有i只白鼠j只黑鼠的状态下王妃获胜的概率是dp[i][j]，这种状态可由一下三种状态得到：

王妃第一次就取得一只白鼠获胜，概率为i/(i+j)；

王妃没有取到白鼠，取黑鼠的概率是j/(i+j)，若王妃要赢，下次龙一定取黑鼠，概率为(j-1)/(i+j-1)，同时跑掉的是黑鼠，概率为(j-2)/(i+j-2)，状态转移到dp[i][j-3];

王妃没有取到白鼠，取黑鼠的概率是j/(i+j)，若王妃要赢，下次龙一定取黑鼠，概率为(j-1)/(i+j-1)，同时跑掉的是白鼠，概率为i/(i+j-2)，状态转移到dp[i-1][j-2];

综上，dp[i][j] = i/(i+j) + j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3] + j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2]。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                //#define LL __int64 #define LL long long #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; double dp[1010][1010]; int main() { int w,b; while(~scanf(%d %d,&w,&b)) { for(int i = 1; i <= w; i++) dp[i][0] = 1; for(int i = 0; i <= b; i++) dp[0][i] = 0; for(int i = 1; i <= w; i++) { for(int j = 1; j <= b; j++) { dp[i][j] = i*1.0/(i+j); if(j >= 2) dp[i][j] += j*1.0/(i+j) * (j-1)*1.0/(i+j-1) * (i*1.0)/(i+j-2) * dp[i-1][j-2]; if(j >= 3) dp[i][j] += j*1.0/(i+j) * (j-1)*1.0/(i+j-1) * (j-2)*1.0/(i+j-2) * dp[i][j-3]; } } printf(%.9lf ,dp[w][b]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：CodeForces 91B Queue （线段树单..	下一篇：C++ Primer 4th 读书笔记(第一部..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: