DP Training J 简单期望DP

DP Training J 简单期望DP

题意

有(N)个盘子，盘子中装有(a_i)个寿司，每次等概率地选择一个盘子来吃一个寿司，若盘子空则不吃。

问期望多少次选择能吃完所有寿司

[1leq N le 300\ 1leq a_i leq3 ]

分析

(a_i)特别小，考虑其特殊性。

(dp[a][b][c])表示还有1个寿司的盘子有(a)个，还有2个寿司的盘子有(b)个，3个的盘子有(c)个，此时期望选择多少次能吃完

[dp[0][0][0] = 0 \ d = a + b + c\ dp[a][b][c] = n / d + dp[a - 1][b][c] cdot a / d + dp[a + 1][b-1][c]cdot b / d + dp[a][b + 1][c - 1] cdot c / d ]

代码

double dp[305][305][305];
int a[30];
int n;

double dfs(int a,int b,int c){
	if(!a && !b && !c) return 0;
	if(dp[a][b][c] > -1 ) return dp[a][b][c];
	int d = a + b + c;
	double ans = 1.0 * n / d;
	if(a) ans += dfs(a - 1,b,c) * a / d;
	if(b) ans += dfs(a + 1,b - 1,c) * b / d;
	if(c) ans += dfs(a,b + 1,c - 1) * c / d;
	return dp[a][b][c] = ans;
}

int main(){
	n = rd();
	for(int i = 0;i < n;i++)
		a[rd()]++;
	memset(dp,-1,sizeof dp);
	dp[0][0][0] = 0;
	printf("%.10f",dfs(a[1],a[2],a[3])); 
}