UVa 11427 (期望 DP) Expect the Expected

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

设d(i, j)表示前i局每局获胜的比例均不超过p，且前i局共获胜j局的概率。

d(i, j) = d(i-1, j) * (1-p) + d(i-1, j-1) * p

则只玩一天就就不再玩的概率Q = sum{d(n, i) | 0 ≤ i ≤ p*n}

那么期望为

这是一个无穷级数，可以用高数的一些知识来解决。

另1-Q = t

将1-Q带入t，并将左边的Q乘过去得：

书上还介绍了一种更简单的方法，假设所求期望为e

第一天玩完就去睡觉，概率为Q，期望为1；第一天玩得高高兴兴，概率为1-Q，期望为1+e

于是有等式：e = Q + (1-Q)(1+e)

#include <cstdio>
#include <cstring>
const int maxn = + ; double d[maxn][maxn]; int main()
{
//freopen("in.txt", "r", stdin); int T;
scanf("%d", &T);
for(int kase = ; kase <= T; kase++)
{
int n, a, b;
scanf("%d/%d%d", &a, &b, &n);
double p = (double)a / b;
memset(d, , sizeof(d));
d[][] = ; d[][] = ;
for(int i = ; i <= n; i++)
for(int j = ; j*b <= a*i; j++)
{
d[i][j] = d[i-][j]*(-p);
if(j) d[i][j] += d[i-][j-]*p;
} double Q = ;
for(int i = ; i*b <= a*n; i++) Q += d[n][i];
printf("Case #%d: %d\n", kase, (int)(/Q));
} return ;
}