【概率】Uva 10900 - So you want to be a 2n-aire?

写完这题赶紧开新题...

话说这题让我重新翻了概率论课本，果然突击完了接着还给老师了，毫无卵用。

很多人拿这位大神的题解作引，在这我也分享给大家~

对于其中的公式在这里做一点简要的说明。因为自己也是理解了一会儿才明白的。

TIPs:

1、设d[i]为答对第i道题后拥有奖金的期望值。

2、对于第i+1道题，我们可以有两种选择：答，不答；

如果不答，那么奖金便到2ⁱ为止；

如果答，答错的话，奖金当然为0；答对的话，奖金会变为P*d[i+1]（这是一个期望值，也可以说是平均值，或者可以这样理解，选择答题的话获得奖金的期望=(1-P)*0 + P*d[i+1]，答错没奖金，答对的话奖金当然就是它咯）；

现在问题来了，此处的P为答对第i+1题的概率，这个概率会是多少呢。

首先我们考虑一个问题，什么情况下你会选择答题？

还用想啊当然是答题的奖金期望比不答的多咯！这也就是：

P*d[i+1] > 2ⁱ（注意此处答对第i+1题的奖金期望并不是2^i+1）

转化一下就是,这个P>2ⁱ/d[i+1]的时候，答对题目拿奖金的概率就会比较大，我们会选择答题；

令ep=2ⁱ/d[i+1]，考虑tmp的范围：

当ep<t时，因为选手答对题的概率在(t,1)间均匀分布，所以选手答对题目的概率会很大，那么我们会让选手答题，答题的概率为(1-max(t,ep))/(1-t);

当ep>t时，选手答对与答错的判断不确定，选择答题的概率为(1-max(t,ep))/(1-t);

注意此处的max(t,ep)，如果ep<t的话答题的概率为(1-t)/(1-t)；而如果ep>t，根据均匀分布的分布函数我们可以知道答题的概率为(1-ep)/(1-t)，故可以化为一个式子(1-max(t,ep))/(1-t);

而之前讨论的答对题目的概率P，因为ep<P<1，根据均匀分布的数学期望可知E_P=(1+ep)/2;

3、那么我们现在可以求答对第i题后奖金的期望值d[i]了：

我们选择不答的概率为(ep-t)/(1-t)，此时拿奖金2ⁱ

我们选择答题的概率为(1-ep)/(1-t)，此时拿奖金(1+ep)/2 * d[i+1];

故d[i]=(ep-t)/(1-t) * 2ⁱ+ (1-ep)/(1-t) * ((1+ep)/2*d[i+1]);

4、这题需要逆推，一共i道题，那么d[i]=2ⁱ

最后求d[0]即可。

代码就不附了吧...

巴特西