题意分析

玩家初始奖金为1美元，需回答$n$个问题。每回答一个问题：

• 若选择回答且答对，奖金翻倍；若答错，奖金清零并结束游戏。
• 若选择不回答，可保留当前奖金并结束游戏。

每个问题的答对概率$p$是在区间$[t, 1]$内均匀分布的随机变量。玩家需采用最优策略（即根据当前$p$决定是否回答），使得期望奖金最大化。

解题思路

1. 动态规划思想：

   • 从最后一个问题向前逆推，计算在每个问题处的最优决策（回答或放弃）。
   • 定义$ans$为从当前问题开始到游戏结束的最大期望奖金。

2. 临界概率判断：

   • 对于每个问题，存在一个临界概率$p = \frac{v[i]}{ans}$，其中$v[i]$是当前问题的奖金。
   • 当$p \leq t$时，所有可能的$p$都满足$p \geq \frac{v[i]}{ans}$，此时回答问题的期望更高。
   • 当$p > t$时，需分区间计算期望：
     • 若$p < \frac{v[i]}{ans}$，选择放弃，获得奖金$v[i]$。
     • 若$p \geq \frac{v[i]}{ans}$，选择回答，期望奖金为$ans$。

3. 数学公式推导：

   • 当$p \leq t$时，期望奖金为$\frac{1+t}{2} \times ans$。
   • 当$p > t$时，期望奖金为$\frac{v[i] \times (p-t) + ans \times \frac{1+p}{2} \times (1-p)}{1-t}$。

代码解释

#include <cstdio>
#include <cmath>

double v[31]; // 存储奖金值v[i] = 2^i

// 预处理2的幂次方
void precompute() {
    v[0] = 1.0;
    for(int i = 1; i <= 30; ++i) 
        v[i] = v[i-1] * 2;
}

// 计算最优策略下的期望奖金
double solve(int n, double t) {
    double ans = v[n]; // 初始化为最后一道题的奖金
    
    // 从倒数第二个问题向前递推
    for(int i = n-1; i >= 0; --i) {
        double p = v[i] / ans; // 计算临界概率
        
        if(p <= t) {
            // 所有可能的p都满足p >= v[i]/ans，选择回答
            ans = (1.0 + t) / 2.0 * ans;
        } else {
            // 分区间计算期望
            double case1 = v[i] * (p - t) / (1.0 - t); // 放弃回答的期望
            double case2 = ans * (1.0 + p) / 2.0 * (1.0 - p) / (1.0 - t); // 继续回答的期望
            ans = case1 + case2;
        }
    }
    return ans;
}

int main() {
    precompute();
    int n;
    double t;
    
    // 处理输入
    while(scanf("%d%lf", &n, &t) == 2) {
        if(n == 0 && t == 0) break;
        printf("%.3lf\n", solve(n, t));
    }
    
    return 0;
}

关键细节

1. 预处理：

   • 预先计算$2^i$的值，存储在数组$v$中，避免重复计算。

2. 逆推过程：

   • 从最后一个问题开始向前计算，每次根据当前奖金和后续期望奖金计算最优决策。

3. 临界概率处理：

   • 当$p \leq t$时，所有可能的$p$都使得回答问题的期望更高。
   • 当$p > t$时，需根据$p$的分布分区间计算期望，综合考虑放弃和回答两种情况。

4. 精度控制：

   • 使用printf("%.3lf\n", ...)确保输出结果保留三位小数。

复杂度分析

• 时间复杂度：$O(n)$，其中$n$是问题数量。
• 空间复杂度：$O(1)$，仅需常数级额外空间。

该算法通过逆推和数学期望的计算，高效地解决了最优策略选择问题，适用于题目给定的$n \leq 30$的范围。