P10504 守卫者的挑战，标签是“期望”和“动态规划”，难度定格在普及+。看到这个组合的时候我就知道，这题不是那种套个模板就能过的水题，它把概率、期望、背包容量和 DP 状态设计揉在了一起，稍不注意就会在边界处理上栽跟头。我最早写这题的时候，第一版代码跑出来的答案居然大于 1，排查了半天才发现是容量数组越界和初始化位置不对两个问题叠在一起。这也是我想写这篇东西的原因：题解开头几句话都能看懂，但真正从零写到 AC，中间的全是细节。
这道题适合正在学 DP、想接触期望/概率 DP 的选手。它没有用到复杂的期望公式，核心就是“把概率当成一种可以累加的量，按阶段推下去”。如果你已经会基础线性 DP，花一个下午把这题吃透，对“状态设计”和“边界截断”的理解会上一个台阶。
1. 先从题目说起：守卫者的挑战在问什么
1.1 题面还原与模型提炼
我按自己理解的通用设定来还原一下场景。某个守卫者要依次面对 n 场挑战，每场挑战都有固定的获胜概率。获胜之后他会得到一块碎片，同时可能获得一个容量奖励（这个奖励可正可负，也可能为零）；失败则什么也得不到。初始时他有一个背包容量 k，每块碎片会占据 1 单位容量。如果某次获胜后容量不够装碎片，这块碎片就相当于白拿，会被丢掉。
最终要求是：走完 n 场挑战后，身上至少有 L 块碎片，并且所有碎片都能装进背包。问达成这个目标的概率是多少。
把它抽象成数学问题，其实是一个带约束的随机过程：每场挑战是一次随机事件，获胜概率已知；获胜会同时改变两个量——碎片数量 j 和背包剩余容量 c；失败则两个量都不变。我们要求的是终态满足某些条件的总概率。
输入大体上是：挑战场数 n、目标碎片数 L、初始容量 k，接下来 n 个获胜概率，再接下来 n 个获胜后的容量奖励值。题目里容量奖励的值有正有负，这就是第一个坑：你要是把容量想成“永远非负”，那这题就做不对。
1.2 为什么它配得上“普及+”
这道题最大的特点，是表面看着像概率计算，实际上考你对 DP 状态维度的选择。比赛里很多人第一反应是写一个记忆化搜索或递归枚举所有情况，复杂度直接爆炸；还有人把容量当普通背包做，忽略了“容量可以是负数”这件事。
它配得上普及+，不是因为转移方程本身有多难，而是因为三个点：
- 容量维度需要处理负数，如何映射到数组下标是个容易写错的地方。
- 胜利后的容量变化是“先消耗 1 再奖励 a[i]”，顺序弄反就全错。
- 最终统计答案时，不是把所有容量大于等于 0 的状态都加起来，还要同时满足胜场数达到 L。
这几个点单独拎出来都不算硬核，但叠在一起，对初学者来说足够喝一壶了。如果你已经刷过一些普及组的 DP 题，做这题会觉得很“练手”；如果你刚学完基础 DP 准备进阶，这道题就是很典型的过渡题。
2. 期望DP的核心思路：为什么这样设计状态
2.1 概率DP和期望DP其实是同一套打法
严格来说，这题算的是概率而不是期望，但 OI 里经常把两者挂在一个标签下。它们共用的核心思想是：把随机过程按阶段展开，每个阶段只保留少量关键状态，用递推代替枚举所有可能路径。
打个比方。你抛一枚硬币，正面概率是 p。连续抛三次，想知道“正面至少出现两次”的概率。新手会枚举 8 种情况，老手会写一个递推：用 f[i][j] 表示抛了 i 次后出现 j 次正面的概率，每次正面和反面两条路分别累加。这就是概率 DP 的雏形。
守卫者这道题也一样。你不能枚举所有胜负组合，因为 n 一大就指数爆炸。但你可以按“前 i 场挑战”的顺序一格格推下去，每一格只记录当前赢了几场、背包还剩多少容量，以及到达这个状态的概率。
这里的关键思维转变是：概率不是“状态的值”，而是“状态自带的权重”。我们要维护的是一个概率分布，最后把所有满足条件的状态权重加起来，就是答案。
2.2 三维状态是怎么想出来的
我先说结论：状态定义为 dp[i][j][c]，表示前 i 场挑战结束后，累计获胜 j 场，背包剩余容量为 c 的概率。
为什么需要三个维度？前两个比较好理解：i 是阶段，j 是目标碎片数，没有 j 就无法判断最终是否达到 L。关键是第三个维度 c。
容量会影响碎片是否能被保留，而获胜时容量会变化，失败时容量不变。如果你只记录前二维，胜利之后你不知道碎片能不能放得下，转移就没法写了。所以必须把容量也作为一个维度存下来。
这里有一个很多人初次接触时的困惑：容量到底是什么意思？我建议你把 c 理解成“当前背包还能再装下几块碎片”。如果 c 是负数，那就表示已经透支了，某些碎片因为没有空间被丢掉了。这样理解之后，胜利的转移就很自然：碎片占用 1 格，所以容量少 1，奖励再增加 a[i]，净变化就是 -1 + a[i]。
2.3 容量范围为什么要截断
如果不加思考地让容量维度开得很大，比如初始容量 k 可能很大或者奖励可能很大，那 dp 数组的第三维会大到无法接受。但我们仔细想一下：最终需要的碎片数最多也就 n 块，所以当容量 c 大于等于 n 时，它和 c 等于 n 是等价的，因为后续不会出现超过 n 个碎片需要存放的情形。同样，如果 c 已经负到 -n 以下，说明之前已经透支了至少 n 块碎片，再怎么奖励也补不回来，因为碎片总数最多只有 n。这种情况下，c 等于 -n 和 c 更小也是等价的。
所以容量范围可以安全地限制在 [-n, n] 闭区间内。数组第三维开 2n+1 大小就够了，配合一个偏移量 offset = n，把负数下标映射成非负下标。这一步不是小优化，而是让题目从“没法做”变成“能做”的关键，也是普及+和普及题的一个重要分界。
3. 状态转移方程的推导与边界处理
3.1 转移方程到底怎么推
假设当前已经处理到第 i 场，状态是 dp[i][j][c]。接下来要面对第 i+1 场挑战，这场挑战的获胜概率是 p[i+1]，获胜后容量奖励是 a[i+1]。
如果挑战失败，概率是 1 - p[i+1]，胜场数不变，容量不变，所以：
dp[i+1][j][c] += dp[i][j][c] * (1 - p[i+1])
如果挑战获胜，概率是 p[i+1]，胜场数加 1，容量变化是“先消耗 1 单位给新碎片，再获得 a[i+1] 的奖励”，所以新容量 nc = c - 1 + a[i+1]。得到：
dp[i+1][j+1][nc] += dp[i][j][c] * p[i+1]
这里的 nc 要经过截断处理：
if (nc > n) nc = n; if (nc < -n) nc = -n;
为什么是“先 -1 再 +a”？因为碎片必须占一个格子，奖励容量是额外的。有些人会把顺序写成 c + a[i+1] - 1，结果一样，但思维上容易漏掉“碎片占格”这件事。我建议始终写 c - 1 + a[i]，对应“放入碎片，然后触发奖励”，这样不容易乱。
初始状态只有一个：dp[0][0][k] = 1，表示一场没打、胜场 0、容量就是初始容量。这里的 k 也要先做一次截断，防止初始值超出数组范围。
3.2 容量负数下标与偏移量
C++ 数组不支持负数下标，所以要对容量做偏移映射。统一做法是定义 offset = n，那么真实容量 c 对应的数组下标是 c + offset。也就是说，容量 -n 对应下标 0，容量 0 对应下标 n，容量 n 对应下标 2n。
写转移时，建议全程用真实容量 c 参与计算，只在存取数组时加上偏移量。这样逻辑清楚，不容易出错。比如：
double val = dp[i][j][c + offset]; dp[i+1][j][c + offset] += val * (1 - p[i+1]);
而不是直接拿下标去算容量，那样很容易把偏移量重复加或漏加。
3.3 最终答案的统计条件
很多人最后统计答案时，写成“胜场数大于等于 L 的所有状态都加一遍”，然后就 WA 了。仔细想想：如果你赢了 L 场，但每块碎片都没地方放，背包剩余容量是负数，那这 L 块碎片根本不算“携带在身上”。
所以统计条件是两个同时成立：
- 胜场数 j >= L
- 剩余容量 c >= 0（所有碎片都能装下）
也就是遍历 dp[n][j][c + offset]，当 j >= L 且 c >= 0 时累加。
这里还有一个容易忽略的点：为什么只看 c >= 0 而不是 c >= j - L？因为状态里的 c 已经是扣除所有碎片占用后的剩余容量。碎片积攒到第 j 块时，它早就把容量减掉了。所以只要 c 不小于 0，就说明背包里确实装着 j 块碎片。再加上 j >= L 的条件，就等价于“至少带着 L 块碎片离开”。
4. 代码实现：从暴力到滚动数组优化
4.1 一个能 AC 的滚动数组版本
我直接给出我最终使用的代码，注释写得比较细，你可以对照上面的推导一起看：
#include <bits/stdc++.h> using namespace std; const int MAXN = 205; double dp[2][MAXN][MAXN * 2 + 5]; int main() { int n, L, k; scanf("%d%d%d", &n, &L, &k); vector<double> p(n + 1); vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { int x; scanf("%d", &x); p[i] = x / 100.0; // 题目给的是百分数 } for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } int offset = n; // 容量平移量 if (k > n) k = n; // 初始容量截断 if (k < -n) k = -n; int cur = 0; dp[cur][0][k + offset] = 1.0; // 初始状态 for (int i = 1; i <= n; ++i) { int nxt = cur ^ 1; // 关键：滚动数组一定要把下一层清零 memset(dp[nxt], 0, sizeof(dp[nxt])); for (int j = 0; j <= i - 1; ++j) { for (int c = -n; c <= n; ++c) { double val = dp[cur][j][c + offset]; if (val == 0.0) continue; // 概率为0的状态直接跳过 // 失败：胜场不变，容量不变 dp[nxt][j][c + offset] += val * (1 - p[i]); // 胜利：胜场+1，容量 = c - 1 + a[i] int nc = c - 1 + a[i]; if (nc > n) nc = n; if (nc < -n) nc = -n; dp[nxt][j + 1][nc + offset] += val * p[i]; } } cur = nxt; } double ans = 0.0; for (int j = L; j <= n; ++j) { for (int c = 0; c <= n; ++c) { ans += dp[cur][j][c + offset]; } } printf("%.6lf\n", ans); return 0; }我实测下来，这个版本在常规数据范围内跑得很快。memset 每次清空整层是必不可少的，如果没有这一步，上一层留下的概率会污染下一层的累加结果，出现答案大于 1 这种一眼就能看懂的灵异现象。
4.2 为什么可以滚掉第一维
观察转移方程，dp[i+1] 这一层永远只依赖 dp[i] 这一层，再往前就碰不到了。所以第一维只需要开两层，用 cur 和 nxt 交替即可。这就是滚动数组。
如果你是想先验证思路，也可以直接写三维数组 dp[n+1][n+1][2n+1]。三维版本更好调试，因为每层数据都保留着，可以打印中间过程。我最初的版本就是三维，AC 之后才改成滚动数组。对于 n 在 200 左右的数据，三维内存也不至于爆，大约是 200 * 200 * 401 * 8 字节，约 128MB，比较紧张但通常能过。滚动数组之后就只有 2 * 200 * 401 * 8，约 1.2MB，怎么开都放心。
4.3 两个想当然的优化陷阱
第一，不要试图把容量维度压缩成“容量和胜场的差值”。我试过用 d = c - j 这种组合状态，结果转移写起来非常别扭，因为胜利同时改两个量，差值的变化并不直观。该记两维就记两维，省维度省出来的代码复杂度往往得不偿失。
第二，不要用 float。概率累加是一个不断累积小数的过程，float 的精度在第几百次累加时可能出问题，答案保留 6 位小数时就可能差几个 1e-7。直接用 double，性能在这题的量级下没有任何压力。
5. 实测踩坑记录：WA原因与调试技巧
5.1 容量数组越界是最隐蔽的错误
这题第一坑就是数组越界。当你写下 dp[cur][j][c + offset] 时，如果忘了先对初始 k 截断，或者转移后的 nc 没有截断，数组下标就会跑到负数或超过上限。
最气人的是，在某些编译环境下，数组越界不一定崩溃，而是会改写相邻的内存，导致后面的概率值变成奇怪的小数。我排查过一次，答案稳定地输出 0.000000，怎么推都觉得转移没问题，最后把容量打印出来才发现，有几个状态的下标是负数。
检查手段是：在转移循环里加一句断言，如果下标越界就直接报错，或者把数组开大一圈，用哨兵值观察有没有被改写。实战中，直接把截断逻辑写对是最省事的。
5.2 滚动数组忘记清零
这个问题我犯过不止一次。滚动数组的当前层 cur 存的是上一轮结果，转移时要写入 nxt，如果不 memset，nxt 里会残留非常古老的数据，导致概率累加超过 1。最明显的特征是：输出答案 > 1，或者概率分布明显不对。
清零的位置也有讲究。必须在每轮外层循环开始时就清空 nxt 整层，而不是在写入某个状态前手动清零，那样容易漏。直接 memset(dp[nxt], 0, sizeof(dp[nxt])) 是最可靠的写法。
5.3 理解“期望DP”的统计口径
虽然标签叫期望，但有几类统计口径：有的期望题问“最终概率”，有的问“期望碎片数”。这题问的是概率，所以最后一步是累加满足条件的状态概率。
如果你把代码改成求“期望碎片数”，统计时就不是加 dp 值，而是加 dp * j，然后用最后一层所有状态的概率总和去归一化。很多人看到期望标签就下意识去乘期望值，结果把概率题做成了期望题，方向完全错了。动笔之前先读清楚问题到底问的是概率还是随机变量的均值，能省掉一整晚的调试时间。
5.4 特判要放在初始化之前
题目里目标碎片数 L 有可能是 0。如果 L = 0，那不管挑战结果如何，守卫者带着 0 块碎片离开，概率显然是 1。这个可以直接特判输出 1.0，省得跑完整个 DP 再被精度问题折磨。
初始容量 k 也可能是负数甚至小于 -n。这种情况必须先截断再初始化 dp[0][0][k + offset]，否则第一步就数组越界。我自己就吃过一次亏：k 是负数时，直接拿 k + offset 当下标，结果数组下标还是负数，程序居然还跑出了结果，后来想想都后怕。
5.5 一个方便的调试思路
我调这类概率 DP 的通用方法是：先写一个 n 很小（比如 n = 2 或 n = 3）的暴力枚举程序，把所有情况列出来手算概率，再用 DP 版跑同一个数据，对比答案。
比如 n = 2、L = 1、k = 1，两场概率都是 50%，奖励都为 0，手算很简单：总共 4 种胜负组合，其中至少赢一场且容量够放的概率是 75%。如果 DP 跑出来不是 0.75，把中间 dp 表打印出来，一眼就能看出是转移写错还是统计写错。这个方法虽然土，但对概率 DP 这种“思路容易错、代码一改就全错”的题型，比看十篇题解都有效。
最后说点实在的
我个人做完这题的体会是：期望 DP 也好，概率 DP 也好，本质上都是“用维度换暴力”。你愿意多开一维容量，愿意处理负数下标，愿意老老实实截断边界，问题就一下子从指数级搜索变成多项式递推。
这道题后面其实还能继续扩展。比如把“至少 L 块碎片”改成“求最终碎片数的期望”，状态不用改，统计那一步改成对所有 j 求加权平均就行。再比如把容量奖励改成依赖某些条件的随机值，状态里就得再加维度。这些玩法都是从一个基础模型长出来的。
如果你今天第一次接触这类题，建议照着上面的代码敲一遍，然后把 n = 3 的场景手算验证一遍。跑通了再尝试把三维改成滚动数组，感受一下内存变化。这套流程走完，以后再看到“期望+动态规划”的标签，你就不会觉得它神秘了。
