0w1

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