UVA11427 Expect the Expected

题目大意：每晚打游戏。每晚中，赢一局概率p，最多玩n局，一直玩到胜率严格大于p时才能停止游戏并高高兴兴回家，否则只能打满n局垂头丧气回家。问打游戏的天数的期望。

考虑“垂头丧气回家”的概率

设dp[i][j]表示i天，赢了j天，且胜率小于等于p的概率
dp[i][j] = dp[i-1][j] * (1 - p) + dp[i - 1][j - 1] * p,j/i <= p

初始状态dp[0][0] = 1,dp[0][i] = 0,i > 0

Q = dp[n][0] + dp[n][1] + .... + dp[n][n]

局数期望EX = Q + 2Q(1-Q) + 3Q(1-Q)^2 + ... + iQ(1-Q)^(i-1) + ... 这是一个无穷级数

运用数列中错位相减求和的思想，有

EX = Q + 2Q(1-Q) + 3Q(1-Q)^2 + ... + iQ(1-Q)^(i-1) + ...

(1-Q)EX = Q(1-Q) + 2Q(1-Q)^2 + ... + (i-1)Q(1-Q)^(i-1) + ......

两式相减，有EX = 1 + (1-Q) + (1-Q)^2 + (1-Q)^3 + .... + (1-Q0^i +........ = lim(i->∞) (1 + (1 - Q)^i)/(1 - (1- Q)) = 1/Q

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <cmath> 
 9 #define min(a, b) ((a) < (b) ? (a) : (b))
10 #define max(a, b) ((a) > (b) ? (a) : (b))
11 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
12 inline void swap(int &a, int &b)
13 {
14     long long tmp = a;a = b;b = tmp;
15 }
16 inline void read(int &x)
17 {
18     x = 0;char ch = getchar(), c = ch;
19     while(ch < '0' || ch > '9') c = ch, ch = getchar();
20     while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
21     if(c == '-') x = -x;
22 }
23 
24 const int INF = 0x3f3f3f3f;
25 const int MAXN = 100 + 10;
26 
27 int t,px,py,n,ca;
28 double dp[MAXN][MAXN];
29 
30 int main()
31 {
32     read(t);
33     for(ca = 1;t;--t,++ca)
34     {
35         read(px), read(py), read(n);
36         memset(dp, 0, sizeof(dp));
37         dp[0][0] = 1;
38         for(register int i = 1;i <= n;++ i)
39             for(register int j = 0;j <= n;++ j)
40             {
41                 if(py * j <= px * i)
42                 {
43                     if(j - 1 >= 0) dp[i][j] = dp[i - 1][j] * (1 - (double)px / py) + dp[i - 1][j - 1] * ((double)px / py);
44                     else dp[i][j] = dp[i - 1][j] * (1 - (double)px / py);
45                 }
46                 else
47                 {
48                     dp[i][j] = 0;
49                     continue;
50                 }
51             }
52         double sum = 0;
53         for(register int i = 0;i <= n;++ i) sum += dp[n][i];
54         int ans = 1 / sum;
55         printf("Case #%d: %d
", ca, ans);
56     }
57     return 0;
58 }

UVA11427