M_sea

UVA10900 So you want to be a 2n-aire?
UVaLuoguVjudge分析感觉还是比较难的...设 $dp_i$ 表示答对第 $i$ 道题后的期望钱数。显然...
扫描右侧二维码阅读全文
30
2019/08

UVA10900 So you want to be a 2n-aire?

UVa

Luogu

Vjudge

分析

感觉还是比较难的...

设 $dp_i$ 表示答对第 $i$ 道题后的期望钱数。显然边界为 $dp_n=2^n$ 。我们要求的是 $dp_0$ 。

考虑转移。设 $\displaystyle r=\frac{2^i}{dp_{i+1}}$ ,那么如果 $t>r$ ,回答第 $i+1$ 个问题的期望更大,所以会选择回答;否则不一定会回答。

可以得到状态转移方程:

$$ dp_i=\begin{cases}\frac{1+t}{2}\times dp_{i+1},&t>r\\\frac{r-t}{1-t}\times2^i+\frac{1-r}{1-t}\times\frac{1+r}{2}\times dp_{i+1},&\mathrm{otherwise}\end{cases} $$

直接逆推即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=30+10;

int n; double t;
double pw[N],dp[N];

int main() {
    for (re int i=pw[0]=1;i<=30;++i) pw[i]=pw[i-1]*2;
    while (n=read()) { scanf("%lf",&t);
        memset(dp,0,sizeof(dp)); dp[n]=pw[n];
        for (re int i=n-1;~i;--i) {
            double r=pw[i]/dp[i+1];
            if (t>r) dp[i]=(t+1)/2*dp[i+1];
            else dp[i]=(r-t)/(1-t)*pw[i]+(1-r)/(1-t)*(1+r)/2*dp[i+1];
        }
        printf("%.3lf\n",dp[0]);
    }
    return 0;
}
最后修改:2019 年 08 月 30 日 08 : 27 PM

发表评论