传送
首先用一个(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
", id, (int)(1 / DP()));
}
return 0;
}