【题目链接】
点击打开链接【思路要点】
补档博客，无题解。【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 5005 #define DONE 1000 double f[MAXN], g[MAXN]; int main() { int T; scanf("%d", &T); while (T--) { int n; double p, q; scanf("%d%lf%lf", &n, &p, &q); n = min(n, DONE); double tmp = p + q - p * q; f[1] = p / tmp; g[1] = q / tmp; for (int i = 2; i <= n; i++) { double tmp, ans, bns; f[i] = 0; tmp = p; ans = (p * (1 - g[i - 1]) + (1 - p) * q * f[i - 1]) / (p + q - p * q); bns = (p * (1 - g[i - 1]) + (1 - p) * (1 - q) * f[i - 1]) / (1 - q + p * q); f[i] = max(f[i], min(ans, bns)); p = 1 - p; ans = (p * (1 - g[i - 1]) + (1 - p) * q * f[i - 1]) / (p + q - p * q); bns = (p * (1 - g[i - 1]) + (1 - p) * (1 - q) * f[i - 1]) / (1 - q + p * q); f[i] = max(f[i], min(ans, bns)); p = tmp; g[i] = 0; tmp = q; ans = (q * (1 - f[i - 1]) + (1 - q) * p * g[i - 1]) / (p + q - p * q); bns = (q * (1 - f[i - 1]) + (1 - q) * (1 - p) * g[i - 1]) / (1 - p + p * q); g[i] = max(g[i], min(ans, bns)); q = 1 - q; ans = (q * (1 - f[i - 1]) + (1 - q) * p * g[i - 1]) / (p + q - p * q); bns = (q * (1 - f[i - 1]) + (1 - q) * (1 - p) * g[i - 1]) / (1 - p + p * q); g[i] = max(g[i], min(ans, bns)); q = tmp; } printf("%.6lf\n", f[n]); } return 0; }