CFR 540 D. Bad Luck Island ( Probability DP )

Problem - 540D - Codeforces
題意：
在一座島上有三種人，只出剪刀，只出石頭，只出布的人。每一秒都有一對人會相見。每對人相見的機率都相同，如果相見的是同一種人，則什麼都不會發生，否則他們會決鬥，就跟一般猜拳規則一樣定勝負，輸的人會死掉。給三種人的初始人數，求每種人分別最終成為島上唯一種族的機率。
解法：
dp[ i ][ j ][ k ][ t ] : 有 i 個石頭人，j 個剪刀人，k 個布人，石頭 / 剪刀 / 布 人成為最終唯一種族的機率。
轉移詳見代碼。
p.s.
一開始想用 bottom-up，發現不太好寫。。。還真不要只習慣寫一種好啊，該判斷什麼時候什麼比較好寫才是。

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