「BZOJ 3029」守卫者的挑战 - 概率与期望

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

题意描述

HydroOJ 链接

打开了黑魔法师 Vani 的大门，队员们在迷宫般的路上漫无目的地搜寻着关押 applepi 的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为 \(k\) 的包包。

擂台赛一共有 \(n\) 项挑战，各项挑战依次进行。第 \(i\) 项挑战有一个属性 \(a_i\)，如果 \(a_i \ge 0\)，表示这次挑战成功后可以再获得一个容量为 \(a_i\) 的包包；如果 \(a_i=-1\)，则表示这次挑战成功后可以得到一个大小为 \(1\) 的地图残片。地图残片必须装在包包里才能带出擂台，包包没有必要全部装满，但是队员们必须把获得的所有的地图残片都带走（没有得到的不用考虑，只需要完成所有 \(n\) 项挑战后背包容量足够容纳地图残片即可），才能拼出完整的地图。并且他们至少要挑战成功 \(l\) 次才能离开擂台。

队员们一筹莫展之时，善良的守卫者 Nizem 帮忙预估出了每项挑战成功的概率，其中第 \(i\) 项挑战成功的概率为 \(p_i\%\)。现在，请你帮忙预测一下，队员们能够带上他们获得的地图残片离开擂台的概率。

解题思路

本题可 DP 解决。我们设 \(f_{i, j, m}\) 为遍历到第 \(i\) 次挑战时，成功了 \(j\) 次，剩余背包为 \(m\) 时的概率。\(m\) 可以为负，可从计入答案的后面成功的挑战中补回来。

最终答案为 \(\sum\limits_{i = l}^n{\sum\limits_{j \ge 0}{f_{n, i, j}}}\)。

显然状态转移方程如下：

\[ f_{i, j + 1, m + a_i} = f_{i, j + 1, m + a_i} + f_{i - 1, j, m} \times p_i \\ f_{i, j, m} = f_{i, j, m} + f_{i - 1, j, m} \times (1 - p_i) \]

在写代码的时候可以优化两点：

  • 为避免下标为负，可将所有下标 \(m\) 增加一个常值 \(\text{MAXN}\)。
  • 为避免越界，可将背包边界限定为 \(\text{MAXN} + n\)，限定为该值可在不越界的情况下统计答案时将所有的合法背包容量统计纳入统计。

代码演示

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
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <algorithm>

const int MAXN = 200;

int main() {
    int n, l, k;
    static double p[MAXN + 1];
    static int a[MAXN + 1];

    scanf("%d %d %d", &n, &l, &k);
    k += MAXN;

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

    static double f[MAXN + 1][MAXN + 1][2 * MAXN + 1];
    f[0][0][k] = 1;
    int left = k, right = k;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            for (int m = left; m <= right; m++) {
                if (f[i - 1][j][m] != 0) {
                    f[i][j + 1][std::min(MAXN + n, m + a[i])] += f[i - 1][j][m] * p[i];
                    f[i][j][m] += f[i - 1][j][m] * (1.0 - p[i]);
                }
            }
        }

        if (a[i] == -1) left--;
        else right += a[i];
    }

    double ans = 0;
    for (int i = l; i <= n; i++) {
        for (int j = MAXN; j <= right; j++) {
            ans += f[n][i][j];
        }
    }

    printf("%.6f\n", ans);

    return 0;
}