CodeForces-148D Bag of mice（概率DP）

传送门：CodeForces - 148D

题目描述

The dragon and the princess are arguing about what to do on the New Year’s Eve. The dragon suggests flying to the mountains to watch fairies dancing in the moonlight, while the princess thinks they should just go to bed early. They are desperate to come to an amicable agreement, so they decide to leave this up to chance.

They take turns drawing a mouse from a bag which initially contains w white and b black mice. The person who is the first to draw a white mouse wins. After each mouse drawn by the dragon the rest of mice in the bag panic, and one of them jumps out of the bag itself (the princess draws her mice carefully and doesn’t scare other mice). Princess draws first. What is the probability of the princess winning?

If there are no more mice in the bag and nobody has drawn a white mouse, the dragon wins. Mice which jump out of the bag themselves are not considered to be drawn (do not define the winner). Once a mouse has left the bag, it never returns to it. Every mouse is drawn from the bag with the same probability as every other one, and every mouse jumps out of the bag with the same probability as every other one.

输入描述

The only line of input data contains two integers $w$ and $b$ $(0 ≤ w, b ≤ 1000)$.

输出描述

Output the probability of the princess winning. The answer is considered to be correct if its absolute or relative error does not exceed $10^{-9}$.

思路分析

• 有w个白耗子，b个黑耗子，公主和龙一起抓耗子，谁先抓到白耗子，谁就赢
• 龙抓一次耗子，会吓跑一只耗子（这只耗子不算谁赢），而公主不会

我们可以定义一个dp数组，dp[i][j]表示有i只白耗子和j只黒耗子的时候公主赢的概率，每一轮的顺序是公主先抓，龙抓，耗子跑。我们只需要推出公主有赢的可能的状态，那么有三种。

• 公主抓到白耗子：dp[i][j]+= i / ( i + j )
• 公主抓到黒耗子，龙抓到黒耗子，黒耗子跑了：dp[i][j] = ( j / (i + j) ) * ( (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) ) * dp[i][j - 3]
• 公主抓到黒耗子，龙抓到黒耗子，白耗子跑了：dp[i][j] = ( j / (i + j) ) * ( (j - 1) / (i + j - 1) * i / (i + j - 2) ) * dp[i - 1][j - 2]
• 记得初始化数组，dp[i][0]=1

样例输入

1 3

样例输出

0.500000000

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int INF = 0x3f3f3f3f;
const int N=1010;

 
double dp[N][N];
 
int main() {
    
    int a,b;
    cin>>a>>b;
    for(int i=1;i<=a;i++)
        dp[i][0]=1;
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            dp[i][j] += (double) i / (i + j);
            if(j >= 2)
                dp[i][j] += (double) j / (i + j) * (double) (j - 1) / (i + j - 1) * (double) i / (i + j - 2) * dp[i - 1][j - 2];
            if(j >= 3)
                dp[i][j] += (double) j / (i + j) * (double) (j - 1) / (i + j - 1) * (double) (j - 2) / (i + j - 2) * dp[i][j - 3];
        }
    }
    printf("%.9lf\n",dp[a][b]);
    return 0;
}