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