传送
首先用一个\(O(n^2)\)的dp求出当晚垂头丧气的概率\(p\).(\(dp[i][j]\)表示玩了\(i\)盘,赢了\(j\)盘的概率,转移显然)。
那么答案就是\(ans = \sum_{i=1}^{+\infty} i * (1 - p) ^{i-1} * p\).
先把正无穷看成\(n\),然后这个可以用错位相减求出前\(n\)项和,然后把\(n\)取极限,就得到了\(ans=\frac{1}{p}\).
不过要是熟悉期望的话,我们可以直接列出这个式子:\(E=p+(1-p)(E+1)\),解出来也是\(E=\frac{1}{p}\).
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e3 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, p1, p2;
db p;
db dp[maxn][maxn];
In db DP()
{
dp[0][0] = 1; db ans = 0;
for(int i = 1; i <= n; ++i)
{
dp[i][0] = dp[i - 1][0] * (1 - p);
for(int j = 1; j <= i; ++j)
{
dp[i][j] = dp[i - 1][j] * (1 - p) + dp[i - 1][j - 1] * p;
if(j * p2 > i * p1) ans += dp[i][j], dp[i][j] = 0; //写break更好
}
}
return 1 - ans;
}
int main()
{
// MYFILE();
int T = read();
for(int id = 1; id <= T; ++id)
{
scanf("%d/%d %d", &p1, &p2, &n);
p = 1.0 * p1 / p2;
printf("Case #%d: %d\n", id, (int)(1 / DP()));
}
return 0;
}