CF148D Bag of mice

看到\(w,b \le 1000\)，我们可以大胆猜想复杂度是\(w*b\)的（大雾）
那么我们设\(f[i][j]\)表示，包里还剩下\(i\)只白老鼠，\(j\)只黑老鼠的时候，轮到公主抽，赢的期望。
仔细看了看题意（之前题意看错了，瞎想半天，淦。），我们可以发现，公主输会发生在两种情况下：
一：包里没有白老鼠了；二：公主抽到了黑老鼠而龙抽到了白老鼠。
同时，对于一个局面，公主胜利的概率有两部分；
一：公主抽到了白球。二：公主的状态转移到的状态抽到了白球。
我们分类讨论。
首先，依据公主抽到白球的概率是\(\frac{i}{i+j}\)，我们可以知道：
$$f_{i,j}+=\frac{i}{i+j}$$
然后，用填表法，我们发现，公主抽到了黑老鼠且龙抽到黑老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}$$
在这种情况下，跑出一只白老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}$$
跑出一只黑老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
所以得到转移方程：
$$f_{i,j}=\frac{j}{i+j}*\frac{j-1}{i+j-1}+f_{i-1,j-2}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}+$$
$$f_{i,j-3}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
于是填表法可得解。

#include<iostream>
#include<cstdio>
using namespace std;
int w,b;
double f[1005][1005];
void init(){
    scanf("%d%d",&w,&b);
    for(int i=1;i<=w;++i){
        for(int j=1;j<=b;++j){
            f[i][j]=0;
        }
    }
    for(int i=1;i<=w;++i){
        f[i][0]=1;
    }
    for(int i=1;i<=b;++i){
        f[0][i]=0;
    }
    for(int i=1;i<=w;++i){
        for(int j=1;j<=b;++j){
            f[i][j]+=(double)i/(i+j);
            if(j>=2){
                f[i][j]+=f[i-1][j-2]*(double)j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2);
            }
            if(j>=3){
                f[i][j]+=f[i][j-3]*(double)j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2);
            }
        }
    }
    printf("%.9lf",f[w][b]);
}
int main(){
    init();
    return 0;
}