题目意思是,公主和龙比赛从一个具有w个白老鼠,b个黑老鼠的袋子里拿老鼠出来。如果公主从袋子里拿出白老鼠就算公主赢。但是每次龙拿出一只老鼠时还会跳出一只老鼠,跳出的老鼠不管是黑是白都与这次谁输赢无关,但是如果最后公主都没抓到白老鼠,那么龙赢。


设dp[i][j]为目前剩下i只白老鼠,j只黑老鼠时公主赢的概率。那么当j==0时,公主必赢,否则就有几种情况。

dp[i][j] = ∑(公主直接拿到白老鼠+公主抓黑的,龙抓黑的,跳出黑色+公主抓黑的,龙抓黑的,跳出白色)

1、dp[i][j] = 1.0*i/(i+j);  //公主直接拿到白老鼠,赢

double bb = 1.0*j/(i+j)*(1.0*(j-1)/(i+j-1));  //两只黑色

2、dp[i][j] = bb*(1.0*(j-2)/(i+j-2))*dp[i][j-3];    //公主抓黑的,龙抓黑的,跳出黑色

3、dp[i][j] = bb*(1.0*i/(i+j-2))*dp[i-1][j-2];      //公主抓黑的,龙抓黑的,跳出白色


(注意2、3情况时必须要存在那么多老鼠可以抓的情况,不然GG)


代码:

StatusAccepted
Time62ms
Memory9952kB
Length720
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=1005;
double dp[maxn][maxn];
int w, b;
int main()
{
    while(~scanf("%d%d", &w, &b)){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=w;i++)dp[i][0]=1;
        for(int i=1;i<=w;i++)
        for(int j=1;j<=b;j++)
        {
            dp[i][j]+=1.0*i/(i+j);  //赢
            double bb=1.0*j/(i+j)*(1.0*(j-1)/(i+j-1));  //两只黑色
            if(j>=3){
                dp[i][j]+=bb*(1.0*(j-2)/(i+j-2))*dp[i][j-3];    //跳出黑色
            }
            if(i>=1&&j>=2){
                dp[i][j]+=bb*(1.0*i/(i+j-2))*dp[i-1][j-2];      //跳出白色
            }
          }
        printf("%.9lf\n",dp[w][b]);
    }
    return 0;
}