「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;
}