bzoj 2318 spoj 4060(KPGAME)

Description

Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。

现在Alice先手投掷硬币，假设他们都想赢得游戏，问你Alice胜利的概率为多少。

Solution

设 f[i]为i个石子A先手获胜的概率，g[i]为A后手获胜的概率

观察到，如果 f[i−1]>g[i−1]的话 ，A显然是不愿意再取石子的，同样B为了获胜也不愿意取石子。

反之 f[i−1]<g[i−1]的话 ，双方都想取石子，那么显然的

f[i]=p∗g[i−1]+(1−p)∗g[i]

g[i]=q∗f[i−1]+(1−q)∗f[i]

把 f[i],g[i]带进去可解得

f[i]=p∗g[i−1]+(1−p)∗q∗f[i−1]1−(1−p)∗(1−q)

g[i]=q∗f[i−1]+(1−q)∗p∗g[i−1]1−(1−p)∗(1−q)

搞定~

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline void read(int &t) {
    int f = ;char c;
    while (c = getchar(), c < '0' || c > '9') if (c == '-') f = -;
    t = c - '0';
    while (c = getchar(), c >= '0' && c <= '9') t = t *  + c - '0';
    t *= f;
}
const int N = ;
double f[N], g[N];
int main() {
    int T, n;
    read(T);
    while (T--) {
        read(n);
        n = min(n, );
        double p, q;
        scanf("%lf%lf", &p, &q);
        f[] = , g[] = ;
        for (int i = ; i <= n; ++i) {
            if (f[i - ] > g[i - ])    p =  - p, q =  - q;
            f[i] = (p * g[i - ] + ( - p) * q * f[i - ]) / ( - ( - p) * ( - q));
            g[i] = (q * f[i - ] + ( - q) * p * g[i - ]) / ( - ( - p) * ( - q));
            if (f[i - ] > g[i - ])    p =  - p, q =  - q;
        }
        printf("%.8lf\n", f[n]);
    }
    return ;
}