Atcoder D - increment of coins (probability DP)

Topic link ：D - increment of coins

The question ：  There are gold coins in the current bag A gold , silver B gold , Copper C gold , If a coin in the bag exceeds 100 individual , End . Take out a coin from the bag with equal probability every time , Then put two coins of the same kind back in the bag . Calculate the expectation of the number of operations .(A,B,C<=99)

analysis ： This is a classic probability DP subject , set up f[i][j][k] Indicates that there are currently i gold A COINS ,j gold B COINS ,k gold C The expected number of coins .

Let's take a look at how to perform state transition ：
Let's say that there is i gold A COINS ,j gold B COINS ,k gold C COINS , Then take it out next time A The probability of coins is A/(A+B+C), Similarly take out B Coins and C The probability of coins is B/(A+B+C) and C/(A+B+C), Then the expected number of our current state is the expected number of our next enumeration state * Its transition probability plus the number of times required for the current state transition . in other words

f[A][B][C]=1+A/(A+B+C)*f[A+1][B][C]+B/(A+B+C)*f[A][B+1][C]+C/(A+B+C)*f[A][B][C+1]

Because the status we need for the current state transition has not been updated , So we can use memory search to update , The boundary condition is A,B,C One of the values is greater than or equal to 100, See code for details ：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=1e2+10;
double f[N][N][N];
//f[i][j][k] The current is i gold A COINS ,j gold B COINS ,k gold C The expected number of coins  
double dfs(int x,int y,int z)
{
	if(x>=100||y>=100||z>=100) return 0;
	if(f[x][y][z]>0) return  f[x][y][z];
	f[x][y][z]=1.0;
	f[x][y][z]+=1.0*x/(x+y+z)*dfs(x+1,y,z);
	f[x][y][z]+=1.0*y/(x+y+z)*dfs(x,y+1,z);
	f[x][y][z]+=1.0*z/(x+y+z)*dfs(x,y,z+1);
	return f[x][y][z];
}
int main()
{
	int n,m,l;
	cin>>n>>m>>l;
	printf("%.10lf",dfs(n,m,l));
	return 0;
}