CodeForces - 148D Bag of mice【概率DP】-蒲公英云

CodeForces - 148D Bag of mice【概率DP】

Pear和Fish正在进行这样一个游戏：

一个袋子里一开始装着w个白球和b个黑球。从Pear开始，每次轮流随机抽出一个球。如果抽出的球是白色的，则抽出这个球的人立即获胜。每当一个球被取出后（然后结算获胜情况后），会有另一个球自动滚出来（不算任何人抽的）。每个人抽球、和自动滚出来的球都是等概率的。那么Pear获胜率是多少呢？

Input

两个数w,b含义如上。w,b<=1000

Output

Pear获胜的概率，保留至少10位小数。

思路：这题用记忆化搜索写比较方便，f[i][j][2] 表示剩下i个白球，j个黑球时先手能赢的概率，0是轮到先手，1是轮到后手了。

转移的时候记忆化一下，然后转移方程比较好想就不细说了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
double f[maxn][maxn][2];
double dfs(int x, int y, int w)
{
    if(x <= 0) return 0;
    if(y <= 0) return w;
    if(f[x][y][w] != -1) return f[x][y][w];
    if(w) //先手
    {
        return f[x][y][w] = x * 1.0 / (x + y) + y * 1.0 / (x + y) * dfs(x, y - 1, w ^ 1);
    }
    else
    {
        return f[x][y][w] = y * 1.0 / (x + y) * (x * 1.0 / (x + y - 1) * dfs(x - 1, y - 1, w ^ 1) + (y - 1) * 1.0 / (x + y - 1) * dfs(x, y - 2, w ^ 1));
    }
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n + 1; ++i)
        for(int j = 0; j <= m + 1; ++j)
            f[i][j][0] = f[i][j][1] = -1;
    double ans = dfs(n, m, 1);
    printf("%.12f\n", ans);
    return 0;
}