题解 | #increment of coins#

【increment of coins】

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

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

状态转移方程为:

dp(i,j,k) = 1.0 + \frac{i \times dp(i + 1,j,k) + j \times dp(i,j + 1,k) + k \times dp(i,j,k + 1)} {i + j + k}

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