【機率dp】zoj3329 One Person Game

題目點這裡

設dp[i]為目前的總點數為i剩餘次數的期望 p[i]表示一次擲骰子總點數為i的機率 p[0]表示三枚骰子點數分别為a b c的機率

則dp[i] = sigma(dp[i + k] * p[k]) + dp[0] * p[0] + 1  ①

設dp[i] = A[i] * dp[0] + B[i]  ②

則dp[i + k] = A[i + k] * dp[0] + B[i + k]  ③

③帶入①得 

dp[i] = sigma(A[i + k] * dp[0] + B[i + k]) * p[k] + dp[0] * p[0] + 1 = (sigma(A[i + k] * p[k]) + p[0]) * dp[0] + sigma(B[i + k] * p[k] + 1)

故 A[i] = sigma(A[i + k] * p[k]) + p[0]    B[i] = sigma(B[i + k] * p[k] + 1)

當i + k > 0時 dp[i + k] = 0 即 A[i + k] = 0 && B[i + k] = 0

是以可以倒推出 A[0] 和 B[0]  然後求出 dp[0] = B[0] / (1 - A[0])

其實有挺多細節要注意的

首先是i + k那裡 k的下界是3不是1   其次是整數相除要記得強轉浮點數   還有就是dp[n] != 0

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

int read()
{
	int sign = 1, n = 0; char c = getchar();
	while(c < '0' || c > '9'){ if(c == '-') sign = -1; c = getchar(); }
	while(c >= '0' && c <= '9') { n = n*10 + c-'0'; c = getchar(); }
	return sign*n;
}

const int Nmax = 525;

int T, N;
int K1, K2, K3, a, b, c, sum; 
double A[Nmax], B[Nmax], p[Nmax];

void dfs(int i)
{
	if(i > N)
	{
		A[i] = B[i] = 0;
		return;
	} 
	if(A[i]) return;
	
	A[i] = p[0], B[i] = 1;
	for(int k = 3; k <= sum; ++k)
	{
		dfs(i + k);
		A[i] += p[k] * A[i + k];
		B[i] += p[k] * B[i + k];
	}
}

int main()
{
	for(T = read(); T-- ; ) 
	{
		N = read(); K1 = read(); K2 = read(); K3 = read();
		a = read(); b = read(); c = read();
		
		memset(p, 0, sizeof(p));
		p[0] = 1.0 / (K1 * K2 * K3); sum = K1 + K2 + K3;
		
		for(int i = 1; i <= K1; ++i)
			for(int j = 1; j <= K2; ++j)
				for(int k = 1; k <= K3; ++k)
					p[i + j + k] += p[0];
					
		p[a + b + c] -= p[0];
		
		memset(A, 0, sizeof(A));
		dfs(0);
		
		printf("%.15f\n", B[0] / (1 - A[0]));
	}
	
	return 0;
}