题解 | #increment of coins#

【increment of coins】

定义$dp(i,j,k)dp(i,j,k)$为背包中分别有$ii$枚金币，$jj$枚银币，$kk$枚铜币时，操作次数的期望。

末态为已经存在某一种硬币有100枚，即 $dp(100,i,j)=dp(i,100,j)=dp(i,j,100)=0;dp(100,i,j)\; =\; dp(i,100,j)\; =\; dp(i,j,100)\; =\; 0;$

状态转移方程为:

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
double dp[N][N][N];
int a, b, c;
int main() {
    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++)
            dp[100][i][j] = dp[i][100][j] = dp[i][j][100] = 0;
    cin >> a >> b >> c;
    for (int i = 99; i >= a; i--)
        for (int j = 99; j >= b; j--)
            for (int k = 99; k >= c; k--)
                dp[i][j][k] = 1.0 + (i * dp[i + 1][j][k] + j * dp[i][j + 1][k] +
                                     k * dp[i][j][k + 1]) /
                                        (i + j + k);
    printf("%.9lf", dp[a][b][c]);
    return 0;
}