UVA 11427 - Expect the Expected

题目链接

题意：玩一个游戏，赢的概率p，一个晚上能玩n盘，如果n盘都没赢到总赢的盘数比例大于等于p，以后都不再玩了，如果有到p就结束

思路：递推，dp[i][j]表示玩i盘，赢j盘的概率,那么一个晚上玩了n盘小于p的概率递推式为：
dp(i,j)=dp(i?1,j)?(1?p)+dp(i?1,j?1)?p
总和为Q=dp(n,0)+dp(n,1)+...+dp(n,x)(x/n<p)

那么每个晚上失败的概率Q就求出来了，那么平均玩的天数的期望就利用全期望公式求得为1/Q

代码：

#include <stdio.h>
#include <string.h>

const int N = 105;
int t, pz, pm, n;
double f[N][N], p;

int main() {
	int cas = 0;
 	scanf("%d", &t);
	while (t--) {
		scanf("%d/%d%d", &pz, &pm, &n);
		p = pz * 1.0 / pm;
		memset(f, 0, sizeof(f));
		f[0][0] = 1;
		double Q = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j * pm <= i * pz; j++) {
				f[i][j] = f[i - 1][j] * (1 - p);
				if (j) f[i][j] += f[i - 1][j - 1] * p;
				if (i == n) Q += f[i][j];
			}
  		}
  		printf("Case #%d: %d\n", ++cas, (int)(1/Q));
  	}
	return 0;
}