abc184_d - Increment Of Coins
11 Dec 2020 — Tags: dp,expected_value,probability — URLI’m kinda :brick: at Probability, so here’s the Editorial.
Time complexity: $O(n^3)$
Memory complexity: $O(n^3)$
Click to show code.
using namespace std;
int const NMAX = 100 + 1;
double dp[NMAX][NMAX][NMAX];
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int a, b, c;
cin >> a >> b >> c;
for (int x = 99; x >= 0; --x)
{
for (int y = 99; y >= 0; --y)
{
for (int z = 99; z >= 0; --z)
{
double d = x + y + z;
dp[x][y][z] = x / d * (dp[x + 1][y][z] + 1) +
y / d * (dp[x][y + 1][z] + 1) +
z / d * (dp[x][y][z + 1] + 1);
}
}
}
cout << setprecision(12) << fixed << dp[a][b][c] << endl;
return 0;
}