# CFR 148 D. Bag of mice ( Probability DP )

Problem - D - Codeforces

dp[ i ][ j ][ k ] : 有 i 隻白老鼠，j 隻黑老鼠，目前為 公主 / 龍 先手的狀態，此時先手的勝率。

p.s. top-down 寫法要特別注意邊界，也就是是否會存取到負值，以及該如何定義。

```int W, B;

void init(){
cin >> W >> B;
}

vvvd dp;
vvvi vis;

void preprocess(){
dp = vvvd( W + 1, vvd( B + 1, vd( 2 ) ) );
vis = vvvi( W + 1, vvi( B + 1, vi( 2 ) ) );
}

double dfs( int w, int b, int t ){
if( b < 0 )
return 0.0; // invalid, but only happens when dragon overdraws
double &res = dp[ w ][ b ][ t ];
if( vis[ w ][ b ][ t ] )
return res;
vis[ w ][ b ][ t ] = 1;
if( w == 0 ) // dragon wins
return res = t;
if( b == 0 )
return res = 1; // any draw is white
if( t == 0 ){ // princess's turn
res += 1.0 * w / ( w + b ); // wins immediately
res += 1.0 * b / ( w + b ) * ( 1.0 - dfs( w, b - 1, t ^ 1 ) ); // dragon does not win
} else{ // dragon's turn
res += 1.0 * w / ( w + b ); // wins immediately
res += 1.0 * b / ( w + b ) * ( 1.0 - ( 1.0 * w / ( w + b - 1 ) * dfs( w - 1, b - 1, t ^ 1 ) + 1.0 * ( b - 1 ) / ( w + b - 1 ) * dfs( w, b - 2, t ^ 1 ) ) );
}
return res;
}

void solve(){
cout << fixed << setprecision( 10 ) << dfs( W, B, 0 ) << endl;
}
```