形式化题目

进行 N 项挑战，第 i 项以概率 $p_i\%$ 成功。初始有一个容量为 $K$ 的包：

• $a_i \geqslant 0$：成功后额外获得容量为 $a_i$ 的包；
• $a_i = -1$：成功后获得 1 个地图残片，每个残片占用 1 单位容量。

全部挑战结束后，记成功次数为 $S$、总容量为 $C = K + \sum a_i$（只累计成功且 $a_i \geqslant 0$ 的项）、残片数为 $F$（成功且 $a_i = -1$ 的项数）。求概率

即成功次数不少于 $L$、且残片全部装得下的概率，输出保留 6 位小数。各挑战是否成功相互独立。

样例 N=3, L=1, K=0、$p=(10,20,30)$、$a=(-1,-1,2)$ 中，合格的成败组合为 $\{3\}$、$\{1,3\}$、$\{2,3\}$、$\{1,2,3\}$，概率之和 $0.216+0.024+0.054+0.006 = 0.300000$；组合 $\{1,2\}$ 虽然成功 2 次，但总容量 0 装不下 2 个残片，不合格。

正解

思路

朴素做法与瓶颈。 最直接的做法是枚举 $2^N$ 种成败组合，逐个判断合格与否并累加概率——N=200 时不可行。把它推进一步：按前缀做 DP，状态记"成功次数 $j$、当前总容量 $c$"，条件判断放到最后。这样组合被共享了，但容量维仍然从 $0$ 到 $K + 1000N = 202000$，三维表 $200 \times 201 \times 202000$ 照样爆炸。两个瓶颈（指数枚举、超大容量维）都需要一个更聪明的状态定义来消除。

第一步：把容量条件改写成净余量。 一个残片消耗 1 单位容量、一个包补充 $a_i$ 单位容量，所以"装得下"等价于一个收支平衡条件。定义

即容量减去残片后的净余量，则 $C \geqslant F \iff t \geqslant 0$。这样一次挑战成功对状态的贡献只有两种：$a_i \geqslant 0$ 时 $t$ 加上 $a_i$，$a_i = -1$ 时 $t$ 减 1；失败则 $t$ 不动。

第二步：成功次数截断到 $L$。 合格条件只问 $S \geqslant L$，超过 $L$ 的部分不再产生任何区别，而且后续转移与 $j$ 的具体取值无关。于是把 $j$ 截断为 $\min(j, L)$，第 $L$ 行吸收所有 $j \geqslant L$ 的状态，行数从 $N+1$ 降到 $L+1$。

第三步：净余量截断到 $[-m, m]$，其中 $m$ 是全题残片总数（$a_i = -1$ 的个数）。 这是本题最关键的观察：

• 上截断 $t \leftarrow \min(t, m)$：被截断的状态必有 $t \geqslant m$，而此后最多再失去 $m$ 个单位（全程残片不超过 $m$ 个，包只会增加容量），最终 $t \geqslant 0$ 恒成立——这类状态"容量一定够"，合并成同一档不改变答案。反方向也成立：截断值永远不超过真实值，所以截断值 $\geqslant 0$ 时真实值也 $\geqslant 0$；而若真实值非负、截断值却跌破 0，它必须先到过顶格 $m$ 再一路下滑 $m$ 格以上，由同样的论证知不可能。因此截断前后"$t \geqslant 0$"的真假完全一致。
• 下界 $t \geqslant -m$：$K \geqslant 0$、包容量非负、残片至多 $m$ 个，收支最坏只差 $-m$，状态不会越出左端。

截断后净余量只有 $2m+1 \leqslant 401$ 个取值（$m \leqslant N \leqslant 200$），即使 $K = 2000$ 也只占一格。状态数降到 $O(L \cdot m)$。

第四步：转移就是"乘权 + 平移"。 设当前挑战成功概率为 $p$、失败概率为 $1-p$，对每一行：

• 失败分支：本行每个格子乘 $(1-p)$，状态不动；
• 成功分支：来源行整行乘 $p$ 后平移——$a_i \geqslant 0$ 时右移 $a_i$ 格（移出顶格的部分全部累加进顶格），$a_i = -1$ 时左移 1 格。成功还会让 $j$ 加 1：第 $j$ 行的成功分支汇入第 $j+1$ 行，封顶的第 $L$ 行则连自身一起汇入（已 $\geqslant L$ 的状态成功后仍在 $L$ 档）。

样例的完整状态演化如下（行 = 成功数档，列 = 净余量 $t$，单元格 = 该状态的累计概率；$m=2$，故列范围 $-2 \sim +2$）：

看三处即可掌握全貌：第 1 项后 $j=1$ 行的 $0.1$ 出现在 $t=-1$ 列，是残片项成功导致的整行左移；第 2 项后 $j=1$ 行的 $0.02 = 0.1 \times 0.2$ 落在 $t=-2$、$0.26 = 0.1 \times 0.8 + 0.9 \times 0.2$ 落在 $t=-1$，说明两个来源（旧 $j=1$ 行自身封顶汇入、旧 $j=0$ 行升档汇入）在同一次转移里叠加；第 3 项后 $j=1$ 行右移 2 格，答案取 $t \geqslant 0$ 的三格之和 $0.006 + 0.078 + 0.216 = 0.3$，与样例输出一致。

实现要点。 初始只有空前缀一种状态：dp[0][min(capacity, frag_total) + frag_total] = 1.0（$K$ 同样先截到 $m$）。前 $i$ 项最多成功 $i$ 次，未达的高档行恒为 0，用 top_j = min(need, i) 跳过；左移分支丢弃的最低格（$t = -m$）在处理任何残片项之前概率恒为 0（此时残片至多成功过 $m-1$ 次，$t \geqslant 1-m$），整段切片操作不会丢概率；$a_i$ 大到超过列宽时，成功质量全部累入顶格，用 gain >= span - 1 分支兜住，避免负下标。

代码

Python 版：

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 18:03
# update_at: 2026-10-01 18:03

import sys


def advance(dp: list[list[float]], p: float, gain: int, span: int, top_j: int) -> list[list[float]]:
    """做一次挑战的单层概率转移：行 = 成功数（截到 L），列 = 净容量（截到 ±m）。

    gain = -1 表示成功得到地图残片（净容量 -1），否则是成功获得的包包容量；
    top_j 是这次转移后可能达到的最大成功数下标（不超过 L）。
    """
    fail = 1 - p
    last_j = len(dp) - 1
    old = [row[:] for row in dp[:top_j + 1]]
    fresh: list[list[float]] = []
    for j, row in enumerate(old):
        nxt = [x * fail for x in row]  # 失败分支：状态原地不动
        if j == last_j:  # 成功数已封顶：成功后仍留在本档
            src = row if j == 0 else [x + y for x, y in zip(row, old[j - 1])]
        elif j > 0:
            src = old[j - 1]
        else:
            src = None
        if src is not None:
            weighted = [v * p for v in src]  # 成功分支：概率加权后的来源行
            if gain < 0:  # 残片：净容量整体左移 1 格（最低格概率恒为 0，可安全舍去）
                nxt[:] = [x + y for x, y in zip(nxt, weighted[1:])] + [nxt[-1]]
            elif gain >= span - 1:  # 增量越过上限，全部截到顶格
                nxt[-1] += sum(weighted)
            else:  # 未越界的左段平移，越界的右段截到顶格
                nxt[-1] += sum(weighted[span - gain:])
                nxt[gain:] = [x + y for x, y in zip(nxt[gain:], weighted)]
        fresh.append(nxt)
    return fresh + dp[len(fresh):]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n, need, capacity = int(next(data)), int(next(data)), int(next(data))  # 挑战数 / 最低成功数 / 初始包容量
    # 成功概率：题面给的是百分数
    probs = [float(next(data)) / 100 for _ in range(n)]
    gains = [int(next(data)) for _ in range(n)]

    # 净容量 = 初始容量 + 获得的包容量 - 地图残片数；只需保留 [-m, m]，m 为残片总数
    frag_total = gains.count(-1)
    span = frag_total * 2 + 1
    dp = [[0.0] * span for _ in range(need + 1)]
    dp[0][min(capacity, frag_total) + frag_total] = 1.0

    for i, (p, a) in enumerate(zip(probs, gains), 1):
        dp = advance(dp, p, a, span, min(need, i))

    # 成功数 ≥ L 的概率全在第 L 行（封顶档），净容量 ≥ 0 即残片装得下
    print(f"{sum(dp[need][frag_total:]):.6f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 18:57
 * update_at: 2026-10-06 18:57
 */

// 概率 DP：状态 = (成功数截到 L, 净余量截到 [-m, m])，
// m 为残片总数，净余量 t = 初始容量 + 成功获得的包容量 - 已得残片数。
// 一次挑战失败：状态原地不动，概率乘 (1-p)；
// 成功：成功数 +1（第 L 档封顶），净余量按 a_i 平移（残片左移 1，包右移 a_i），
// 越过 [-m, m] 边界的概率全部截到边界格（截断不改变最终 t >= 0 的真假）。
// 答案 = 第 L 行中净余量 >= 0 各格概率之和。复杂度 O(N * L * m)。
#include <cstdio>

typedef long long ll;

const int MAXN = 205;
const int MAXT = 405; // 净余量列数最多 2m+1 <= 2N+1

int n;          // 挑战数
ll need;        // 至少要成功的次数 L
ll frag;        // 残片总数 m（a_i = -1 的项数）
ll init_cap;    // 初始包容量 K
double p[MAXN]; // 每项挑战成功的概率（已除以 100）
ll a[MAXN];     // 每项挑战的属性值

// dp[j][t + m]：成功数（截到 L）为 j、净余量（截到 [-m, m]）为 t 的累计概率，
// 列下标整体平移 m 保证非负；滚动时用 cur/newcur 两层
double dp[MAXN][MAXT];
double ndp[MAXN][MAXT];

int span; // 列数 = 2m+1
int top;  // 列下标上限 = span-1（对应净余量 +m）
int base; // 净余量 0 对应的列下标 = m

int main() {
    scanf("%d %lld %lld", &n, &need, &init_cap);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &p[i]);
        p[i] /= 100.0; // 题面给的是百分数
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        if (a[i] == -1) frag++; // 统计残片总数 m
    }

    span = 2 * frag + 1;
    top = span - 1;
    base = frag;

    // 初始状态：0 次成功，净余量 = K（同样先截到 +m）
    dp[0][init_cap > frag ? top : init_cap + base] = 1.0;

    // 逐项做概率转移
    for (int i = 1; i <= n; i++) {
        // 前 i 项最多成功 min(i, L) 次，更高的档恒为 0，直接清零
        ll reach = need < i ? need : i;
        for (ll j = 0; j <= reach; j++)
            for (int t = 0; t < span; t++)
                ndp[j][t] = 0.0;

        for (ll j = 0; j <= reach; j++) {
            for (int t = 0; t < span; t++) {
                double cur = dp[j][t];
                if (cur == 0.0) continue;
                // 失败分支：状态原地不动
                ndp[j][t] += cur * (1.0 - p[i]);
                // 成功分支：成功数 +1（封顶在第 L 档），净余量平移
                ll nj = j + 1 < need + 1 ? j + 1 : need;
                int nt;
                if (a[i] == -1) {
                    // 残片：左移 1 格；t = -m 的格子概率恒为 0（未集齐 m 个残片前
                    // 净余量 >= 1-m），丢弃不丢概率
                    if (t > 0) nt = t - 1;
                    else continue; // t = 0 即净余量 -m，上面论证过概率必为 0
                } else {
                    // 包：右移 a_i 格，越过 +m 的部分截到顶格
                    nt = t + a[i] > top ? top : t + a[i];
                }
                ndp[nj][nt] += cur * p[i];
            }
        }
        for (ll j = 0; j <= reach; j++)
            for (int t = 0; t < span; t++)
                dp[j][t] = ndp[j][t];
    }

    // 成功数 >= L 的概率全部在第 L 档；净余量 >= 0 即残片装得下
    double ans = 0.0;
    for (int t = base; t < span; t++)
        ans += dp[need][t];
    printf("%.6f\n", ans);
    return 0;
}

复杂度

• 时间：每项挑战对至多 $L+1$ 行各做一次失败乘法和一次成功平移，每次 $O(m)$，合计 $O(N \cdot L \cdot m)$，最坏 $200 \times 200 \times 401 \approx 1.6 \times 10^7$，主体是列表推导的 C 级循环，与标准 C++ 正解（滚动概率 DP，同为 $O(N \cdot L \cdot m)$）同阶。朴素容量维做法 $O(N \cdot L \cdot 202000)$ 与枚举 $2^N$ 均被消除。
• 空间：两层滚动概率表各 $(L+1) \times (2m+1)$ 个浮点数，最坏约 $2 \times 201 \times 401 \approx 1.6 \times 10^5$，外加每行等长的临时列表，远低于 128MB。

总结

把"容量够不够装残片"改写成收支平衡的净余量 $t$，两个判定条件就都变成了对聚合量的阈值判断；成功数截到 $L$、净余量截到 $\pm m$，状态数从指数/十万量级压到 $O(L \cdot m)$，逐项转移退化成"失败乘 $(1-p)$ 原地不动、成功整行平移"，最终答案就是第 $L$ 行右半段之和。

图示解析

这张图串起本题从"枚举爆炸"到"截断 + 平移 DP"的主线：

1
2
3
4
5枚举 2^N 种成败组合（指数爆炸）
`- 状态压缩：成功数 j 与 净余量 t = 容量 - 残片数
   `- 双截断：j 截到 L，t 截到 [-m, m]，状态数 O(L·m)
      `- 逐项转移：失败乘 (1-p) 原地，成功整行平移 ±a_i
         `- 答案 = 第 L 行中 t >= 0 各格之和

先看每个节点如何消掉上一层的瓶颈：压缩消掉指数枚举，截断消掉 $K$ 与 $N$ 带来的大维度，平移消掉逐格枚举的三重循环。顺着分支读到最后一行，就是代码里 sum(dp[need][frag_total:]) 这一步的由来。