「BZOJ 4318」OSU! - 概率与期望

我们可以把 osu! 的规则简化与改编成以下的样子:

一共有 次操作,每次操作只有成功与失败之分,成功对应 ,失败对应 次操作对应为 个长度为 的 01 串。在这个串中连续的 可以贡献 的分数,这 不能被其他连续的 所包含(也就是极长的一串 )。

现在给出 ,以及每个操作的成功率,请你输出期望分数。

链接

BZOJ 4318

题解

表示前 次操作后的期望得分, 表示第 次操作成功的概率。

考虑连续 的长度 的变化,如果第 次成功,则 ,考虑其对得分 的影响。

根据期望的线性性,我们只需要求出 ,即可得到

乘上成功的概率,即为该次操作的期望分数增量(相对于第 次)。

考虑如何维护 ,仍旧是考虑期望的线性性,将式子展开。

首先,显然

的概率比上一次操作多 次,有 的概率直接成为 ,即

类似的,有

至此, 均可在线性时间内递推得到。

代码

#include <cstdio>
#include <cmath>

const int MAXN = 100000;

int n;
double p[MAXN + 1], f[MAXN + 1];
double ex1[MAXN + 1], ex2[MAXN + 1];

inline void dp() {
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        ex1[i] = (ex1[i - 1] + 1) * p[i];
        ex2[i] = (ex2[i - 1] + 2 * ex1[i - 1] + 1) * p[i];
        double t = (3 * ex2[i - 1] + 3 * ex1[i - 1] + 1) * p[i];
        f[i] = f[i - 1] + t;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf", &p[i]);

    dp();

    printf("%.1lf\n", floor(f[n] * 10 + 0.5) / 10);

    return 0;
}