CFR 540 D. Bad Luck Island ( Probability DP )

Problem - 540D - Codeforces

dp[ i ][ j ][ k ][ t ] : 有 i 個石頭人，j 個剪刀人，k 個布人，石頭 / 剪刀 / 布 人成為最終唯一種族的機率。

p.s.

```int R, S, P;

void init(){
cin >> R >> S >> P;
}

double dp[ 101 ][ 101 ][ 101 ][ 3 ];
bool vis[ 101 ][ 101 ][ 101 ][ 3 ];

double dfs( int i, int j, int k, int t ){
if( ( not i and not j ) )
return t == 2;
if( ( not j and not k ) )
return t == 0;
if( ( not k and not i ) )
return t == 1;
if( not i )
return t == 1;
if( not j )
return t == 2;
if( not k )
return t == 0;
double &res = dp[ i ][ j ][ k ][ t ];
if( vis[ i ][ j ][ k ][ t ] )
return res;
vis[ i ][ j ][ k ][ t ] = 1;
res += 1.0 * i / ( i + j + k ) * j / ( i + j + k - 1 ) * dfs( i, j - 1, k, t ); // dp[ i ][ j - 1 ][ k ][ t ];
res += 1.0 * i / ( i + j + k ) * k / ( i + j + k - 1 ) * dfs( i - 1, j, k, t ); // dp[ i - 1 ][ j ][ k ][ t ];
res += 1.0 * j / ( i + j + k ) * i / ( i + j + k - 1 ) * dfs( i, j - 1, k, t ); // dp[ i ][ j - 1 ][ k ][ t ];
res += 1.0 * j / ( i + j + k ) * k / ( i + j + k - 1 ) * dfs( i, j, k - 1, t ); // dp[ i ][ j ][ k - 1 ][ t ];
res += 1.0 * k / ( i + j + k ) * i / ( i + j + k - 1 ) * dfs( i - 1, j, k, t ); // dp[ i - 1 ][ j ][ k ][ t ];
res += 1.0 * k / ( i + j + k ) * j / ( i + j + k - 1 ) * dfs( i, j, k - 1, t ); // dp[ i ][ j ][ k - 1 ][ t ];
double d = 1.0;
d -= 1.0 * i / ( i + j + k ) * ( i - 1 ) / ( i + j + k - 1 );
d -= 1.0 * j / ( i + j + k ) * ( j - 1 ) / ( i + j + k - 1 );
d -= 1.0 * k / ( i + j + k ) * ( k - 1 ) / ( i + j + k - 1 );
res /= d;
return res;
}

void preprocess(){
}

void solve(){
for( int i = 0; i < 3; ++i )
cout << fixed << setprecision( 10 ) << dfs( R, S, P, i ) << " \n"[ i + 1 == 3 ];
}
```