UESTC 2015dp专题 F 邱老师看电影概率dp

2022-11-18 07:35:51

邱老师看电影

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/65

Description

一天邱老师心血来潮想去看电影，但是邱老师的妹子想去逛街，他们谁也没有办法说服对方，于是准备来玩一个游戏来决定听谁的。

邱老师找来w只白鼠和b只黑鼠，邱老师和妹子轮流从袋子里面抓老鼠，谁先抓到白色老鼠谁就赢。

但是有酱神在旁边捣乱，邱老师每抓一只老鼠出来，酱神就偷偷的也从里面抓一只出来，这3个人抓出来的老鼠都是随机的。

如果袋子里没有白老鼠，且之前没有人拿到白老鼠的时候，邱老师胜。

为了体现绅士精神，邱老师让妹子先抓，那么妹子赢的概率是多少呐？

wij 千克的蛋糕，Gorwin从左上角(1,1)的格子开始走，走到右下角(n,m)的格子。在每一步中，Gorwin可以向右或者向下走，即是：Gorwin 站在(i,j)的时候，她可以走向(i+1,j)或者(i,j+1) (然而她不能走出这个花园)。当Gorwin到达一个格子的时候，她可以把那个格子里面的蛋糕吃完或者不吃。但是，她不能只吃一部分。她的胃不是那么大，所以她最多只能吃K千克的蛋糕。现在，Gorwin站在左上角，她在看蛋糕园的地图，想要找出一条路，能够使得她吃到的蛋糕最多的一条路。请你来帮帮忙。

Input

只有两个数字 w和b w<=1000 b<=1000

Output

输出妹子赢的概率保留9位小数

Sample Input

1 3

Sample Output

0.500000000

HINT

题意

题解：

概率dp

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

double dp[][];

double dfs(int w,int b)

{

    if(w==) return ;

    if(b==&&w!=) return ;

    if(dp[w][b]>=) return dp[w][b];

    dp[w][b]=w*1.0/(w+b);

    if(b>=)

    {

        double tb=b*1.0/(w+b)*(b-)*1.0/(w+b-);

        if(b>=)

            dp[w][b]+=tb*dfs(w,b-)*(b-)*1.0/(w+b-);

        if(w>=)

            dp[w][b]+=tb*dfs(w-,b-)*(w*1.0)/(w+b-);

    }

    return dp[w][b];

}

int w,b;

int main()

{

    memset(dp,-,sizeof(dp));

    scanf("%d%d",&w,&b);

    printf("%.9f\n",dfs(w,b));

}

码农公寓