UVa 10900 So you want to be a $2^n$-aire? (概率DP)

发表于 更新于 分类于

题目

题目大意

在一个电视娱乐节目中, 你一开始有\(1\)元钱。主持人会问你\(n\)个问题, 每次你听到问题后有两个选择: 一是放弃回答该问题, 退出游戏, 拿走奖金； 二是回答问题。如果回答正确, 奖金加倍; 如果回答错误, 游戏结束, 你一分钱也拿不到。如果正确地回答完所有\(n\)个问题, 你将拿走所有的\(2^n\)元钱, 成为\(2^n\)元富翁。

当然, 回答问题是有风险的。每次听到问题后, 你可以立刻估计出答对的概率。由于主持人会随机问问题, 你可以认为每个问题的答对概率在\(t\)和\(1\)之间均匀分布。输入整数\(n\)和实数\(t\)(\(1 ≤ n ≤ 30\), \(0 ≤ t ≤ 1\)), 你的任务是求出在最优策略下, 拿走的奖金金额的期望值。这里的最优策略是指让奖金的期望值尽量大。

题解

设\(dp_i\)为答对\(i\)题后的最大期望奖金, 答对的概率为\(p\), 则\(dp_i = max(2^{i}, p\ dp_{i + 1})\)。令\(p_0 = max(t, \frac{2^i}{dp_{i + 1}})\), 刘汝佳说可以看出, \(p\)的实际范围是\([t, p_0)\), 因此概率为\(p_1 = \frac{p_0 - t}{1 - t}\)。

根据刘汝佳说的全期望公式, \(dp_i = p_1\ 2^i + \frac{(1 + p_0)(1 - p_1)dp_{i + 1}}{2}\)。

边界是\(dp_n = 2^n\), 逆向推出\(dp_0\)就是答案, 但如果\(t = 1\), 答案则为\(2^n\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <algorithm>
double dp[40], t, p0, p1;
int n;
int main(int argc, char const *argv[]) {
  while (~scanf("%d %lf", &n, &t) && (n || (t != 0.000000))) {
    std::fill(dp, dp + 40, 0.0);
    dp[n] = double(1 << n);
    for (register int i(n - 1); i >= 0; --i) {
      p0 = std::max(t, double(1 << i) / dp[i + 1]),
      p1 = (p0 - t) / (1 - t);
      dp[i] = double(1 << i) * p1 + (1.0 + p0) / 2.0 * dp[i + 1] * (1.0 - p1);
    }
    printf("%.3lf\n", t == 1.000000 ? dp[n] : dp[0]);
  }
  return 0;
}