bzoj2318 Spoj4060 game with probability Problem

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2318

【题解】

令f[i]表示剩i个石子，A先手赢的概率；g[i]表示剩i个石子，A后手赢的概率。

如果想选的话，f[i]可以通过g[i-1]和g[i]转移来，系数推推即可。同理g[i]可以通过f[i-1]和f[i]转移来。

然后这是两个方程，我们要求解的是f[i]和g[i]，解方程 化简即可。

考虑如果f[i-1]<g[i-1]也就是说后手比较优，那么A想让石头来到i-1，这样就出现了i-1石头，B先手A后手，比较优，所以都想选。

反之都不想选。

直接转移即可，复杂度O(Tn)。

考虑复杂度太大，加上打表打表可以知道，当n很大的时候，f和g基本不变，我们设定阈值10w，超过就当做10w做即可。

# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

# define RG register
# define ST static

int T, n;
double p, q;
double f[M], g[M];
// 剩i个石子，A先手赢的概率
// 剩i个石子，A后手赢的概率 

inline void sol() {
    cin >> n >> p >> q;
    f[0] = 0.0, g[0] = 1.0; 
    for (int i=1; i<=n && i<=100000; ++i) {
        if(f[i-1] <= g[i-1]) {
            f[i] = ((1.0-p) * q * f[i-1] + p * g[i-1]) / (1.0-(1-p)*(1-q)); 
            g[i] = ((1.0-q) * p * g[i-1] + q * f[i-1]) / (1.0-(1-p)*(1-q));
        } else {
             f[i] = (p * (1.0-q) * f[i-1] + (1.0-p) * g[i-1]) / (1.0-p*q);
            g[i] = (q * (1.0-p) * g[i-1] + (1.0-q) * f[i-1]) / (1.0-p*q);
        }
    }
    printf("%.6lf
", f[(n > 100000) ? 100000 : n]); 
}

int main() {
    cin >> T;
    while(T--) sol();
    return 0;
}