「洛谷 P1365」Easy - 概率与期望

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

有一种音游的计分方式为在一首歌中有 \(n\) 次点击要做，成功了就是 o，失败了就是 x，分数是按 combo 计算的，连续 \(a\) 个 combo 就有 \(a\times a\) 分，combo 就是极大的连续 o。

Sevenkplus 闲的慌就看他打了一盘，有些地方跟运气无关要么是 o 要么是 x，有些地方 o 或者 x 各有 \(50\%\) 的可能性，用 ? 号来表示。

那么的期望得分是多少？

数据范围：\(n\le3\times10^5\)

解题思路

对于这种期望题，我们可以用 DP 解决。

我们可以定义状态 \(f_i\) 表示在第 \(i\) 次点击中获得分数的期望，同时我们可以定义 \(\text{len}\) 为当前连击数的期望。

我们有以下三种情况：

  1. 第 \(i\) 次点击为 x：显然 \(f_i = f_{i - 1}\)，\(\text{len} = 0\)
  2. 第 \(i\) 次点击为 o：对于连续次 combo 可加的分为 \((\text{len + 1})^2 - \text{len}^2 = 2 \times \text{len} + 1\)，故 \(f_i = f_{i - 1} + 2 \times \text{len} + 1\)，\(\text{len} = \text{len} + 1\)
  3. 第 \(i\) 次点击为 ?：则有 \(50\%\) 为 x，\(50\%\) 为 o。故两种情况求平均值即可。即 \(f_i = \frac{f_{i - 1} + f_{i - 1} + 2 \times \text{len} + 1}{2} = f_{i - 1} + \text{len} + 0.5\)，\(\text{len} = \frac{0 + \text{len} + 1}{2} = \frac{\text{len} + 1}{2}\)

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>

const int MAXN = 300000;

int main() {
    int n;
    static char str[MAXN + 1];

    scanf("%d", &n);
    scanf("%s", str + 1);

    static double f[MAXN + 1];
    double len;

    for (int i = 1; i <= n; i++) {
        switch (str[i]) {
            case 'x':
                f[i] = f[i - 1];
                len = 0;
                break;
            case 'o':
                f[i] = f[i - 1] + 2 * len + 1;
                len++;
                break;
            case '?':
                f[i] = f[i - 1] + len + 0.5;
                len = (len + 1) / 2;
                break;
        }
    }

    printf("%.4lf\n", f[n]);

    return 0;
}