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

川长思鸟来 2023-06-08 03:18 3阅读 0赞

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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round 73 D dp

接：[http://codeforces.com/contest/1221/problem/D][http_codeforces.com_contest_1221_pro...

痛定思痛。/ 2024年04月20日 08:36/ 0 赞/ 96 阅读

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

Pear和Fish正在进行这样一个游戏：一个袋子里一开始装着w个白球和b个黑球。从Pear开始，每次轮流随机抽出一个球。如果抽出的球是白色的，则抽出这个球的人立即获胜。每当

川长思鸟来/ 2023年06月08日 03:18/ 0 赞/ 4 阅读

相关 Codeforces 354 B Pyramid of Glasses （dp）

Pyramid of Glasses time limit per test 1 second memory limit per test 256 megabyte

傷城~/ 2022年08月23日 04:57/ 0 赞/ 150 阅读

相关 codeforces 518D. Ilya and Escalator 概率dp

D. Ilya and Escalator time limit per test 2 seconds memory limit per test 256 megaby

小灰灰/ 2022年08月22日 05:49/ 0 赞/ 56 阅读

相关 codeforces 519D dp

D. A and B and Interesting Substrings time limit per test 2 seconds memory limit per

雨点打透心脏的1/2处/ 2022年07月24日 05:08/ 0 赞/ 216 阅读

相关 codeforces 148D Bag of mice (概率)

The dragon and the princess are arguing about what to do on the New Year's Eve. The drag

r囧r小猫/ 2022年06月04日 06:48/ 0 赞/ 153 阅读

相关 CodeForces 189D(最短路+dp)

问题描述: PMP is getting a warrior. He is practicing a lot, but the results are not accepta

我不是女神ヾ/ 2022年06月02日 05:09/ 0 赞/ 199 阅读

相关浅析Bag-of-words及Bag-of-features

目录 Bag-of-words简介 Bag-of-words应用于图像 Bag-of-features基础流程 1、特征提取 2、学习 “视觉词典（visual vo

缺乏、安全感/ 2022年02月04日 17:51/ 0 赞/ 270 阅读

相关 CF 148D Bag of mice （概率DP）

题目链接：http://codeforces.com/problemset/problem/148/D 题意：袋子里有w只白鼠和b只黑鼠，由公主开始，公主和龙轮流从袋子中抓一

淩亂°似流年/ 2021年11月01日 03:42/ 0 赞/ 257 阅读

相关 CodeForces - 55D Beautiful numbers (数位dp)

Volodya is an odd boy and his taste is strange as well. It seems to him that a positive

偏执的太偏执、/ 2021年09月29日 13:24/ 0 赞/ 414 阅读