第一次在洛谷看到《P1654 OSU!》的题名时我以为又是哪位音游玩家把游戏直接搬进了题库仔细读完题面才发现这其实是一道地地道道的期望动态规划题。题目本身不长给定一个长度为 n 的 01 序列每一位有独立的概率 p_i 为 1连续的 1 构成一段一段长度为 x 的贡献是 x^3最后把所有段的贡献加起来求总得分的期望。很多新手看到这个模型会下意识想把所有连续段找出来一段一段算立方不就行了但 n 一旦来到 10^5 级别朴素的枚举和分段统计都会瞬间失效。这篇内容主要写给正在刷期望 DP 的选手。如果你已经会做“长度平方”的 OSU! 类题目这篇会帮你把思路升级到三次方如果你是第一次接触这类“连续段计分概率”的模型我也建议你跟着推导完整走一遍把“增量贡献”和“维护低阶幂次期望”这套思想真正吃透。P1654 在竞赛圈子里被反复提及不因为它代码长而是因为它把概率、期望、递推和数学展开结合得非常典型吃透它之后很多变式题都会迎刃而解。1. 先搞清楚题目到底在问什么1.1 游戏背景只是外衣核心是连续段计分题目包装成 OSU! 这个下落式音游玩家要跟着节奏点击音符一段连续的点击会带来更高的分数。竞赛题当然不会真去模拟谱面它把机制抽象成了生成一个长度为 n 的 01 序列第 i 位为 1 的概率是 p_i连续的若干 1 组成一段一段长度为 L 的连续 1 对总分的贡献是 L^3所有连续段的贡献相加得到总分总分是一个随机变量求它的数学期望。这里最容易踩的第一个坑是“连续段”的定义。比如序列11011它有两段连续的 1前两个 1 是一段长度为 2贡献 2^3 8后两个 1 是另一段长度也是 2贡献 8总分是 16。不能把中间用 0 隔断的部分硬并成一个长度为 4 的块来算那是错的。0 在序列里既是“没点击”的标志也是连续段的天然分割线。理解了这个定义你才会明白为什么这道题不能简单地对整串做一次立方求和而必须一段一段地处理。1.2 直接枚举或按段统计都会撞上组合爆炸最朴素的做法是枚举所有 2^n 个 01 结果每个结果求一次总分再按概率加权平均。n 20 的时候还能玩n 100000 时这就是天文数字。那按连续段为单位统计行不行理论上可以实际操作很痛苦。一个结果里可能同时出现很多段段与段之间的概率会互相纠缠你要把所有可能的“段集合”都列出来每个集合还要算它的发生概率复杂度指数级上升而且推导极易出错。更聪明的做法是换一个视角。期望有一个性质叫线性性总期望等于每个位置期望贡献之和不需要关心各个位置之间的复杂依赖。只要我能写出“第 i 个位置对总分的新增期望贡献”然后对每个位置求和整道题就拆成了 n 个独立的小问题。1.3 先看一个位置上的“分数增量”假设处理到第 i 个位置之前已经有一段以第 i-1 位结尾的连续 1长度记为 L。如果第 i 位是 1段长从 L 变成 L1这一整段的贡献从 L^3 变成 (L1)^3所以这个位置给总分带来的增量是(L1)^3 - L^3 3L^2 3L 1如果第 i 位是 0连续段在这里断掉这个位置的新增贡献就是 0。第 i 位是 1 的概率是 p_i所以第 i 位的期望增量就是p_i * E[3L^2 3L 1]注意这里的 L 是一个随机变量不能拿一个固定的长度代进去。要对所有位置求和我就需要知道 E[L] 和 E[L^2]。于是问题变成了如何动态维护“以当前位结尾的连续 1 长度”的期望以及它的平方的期望。2. 期望 DP 的完整推导从一次方到三次方2.1 为什么平方版本只需要维护长度期望我们先退一步。如果一段连续 1 的得分是 L 而不是 L^3那第 i 位的新增增量是 (L1) - L 1只要第 i 位是 1 就多拿 1 分期望增量就是常数 p_i根本不需要管 L 具体是多少。所以线性得分对应的是最简单的模型。得分改成 L^2 之后增量公式变成(L1)^2 - L^2 2L 1这个式子里面有 L所以必须维护 E[L]。也就是说平方版本的 OSU! 只需要维护“长度期望”这一个变量。到本题的立方版本增量展开里有 L^2所以还要把 E[L^2] 也一起维护。这种“得分函数升级一次就多维护一个幂次期望”的规律正是这类题的核心骨架。2.2 长度期望和平方期望的递推关系设 X_i 表示处理完前 i 个位置后以第 i 位结尾的连续 1 长度。如果第 i 位是 0那么 X_i 0如果第 i 位是 1那么 X_i X_{i-1} 1。我们令a_i E[X_i]b_i E[X_i^2]根据定义第 i 位为 1 时才会让连续长度延续所以a_i p_i * (a_{i-1} 1)这里乘 p_i 的含义是第 i 位为 1 的概率是 p_i此时长度在旧长度基础上加 1第 i 位为 0 时长度直接变成 0。对期望做加权平均自然就是上面这个式子。同理平方的期望是b_i p_i * E[(X_{i-1} 1)^2]展开平方利用期望的线性性b_i p_i * (b_{i-1} 2 * a_{i-1} 1)这里最关键的一点是b_i 是“随机变量平方的期望”不是“期望的平方”。很多人会把 E[X^2] 和 (E[X])^2 搞混一旦混淆后面整个递推都会偏。2.3 总分期望的累积公式我们真正要算的是总分期望。第 i 位的新增期望增量取决于第 i 位之前的连续长度也就是 X_{i-1}所以应该用更新前的 a_{i-1}、b_{i-1} 来计算ans p_i * (3 * b_{i-1} 3 * a_{i-1} 1)算完这一步再用前面的公式把 a_i、b_i 更新出来供下一轮使用。这个顺序极其重要。a_i、b_i 是已经考虑了第 i 位是 0 的情况后的“新状态”如果先更新它们再用它们去算第 i 位的增量就相当于把第 i 位一定为 1 当成前提了逻辑上完全错位。后面我会专门用一个例子演示错误顺序会偏多少。注意有人可能会想要不要维护 E[X^3]本题累加的是“每个位置的增量期望”增量展开只需要低阶项 X_{i-1}^2 和 X_{i-1}所以不需要维护三次幂期望。只有当题目问的是“处理完整个序列后的连续段长度立方的期望”时才需要维护三阶矩。很多题解里到立方版本也只用三个变量就是这个道理。3. 核心代码实现与更新顺序的坑3.1 滚动变量版本的 AC 代码因为每次只依赖上一轮的状态完全不需要开数组用三个 double 滚动即可。时间复杂度 O(n)空间复杂度 O(1)。下面是 C 版本#include bits/stdc.h using namespace std; int main() { int n; scanf(%d, n); double f 0, g 0, ans 0; // f: 当前连续1长度的期望 E[L] // g: 当前连续1长度平方的期望 E[L^2] for (int i 1; i n; i) { double p; scanf(%lf, p); // 先累加第 i 位的新增期望分数 ans (3 * g 3 * f 1) * p; // 再更新状态注意 g 的更新要用上一轮的 f g (g 2 * f 1) * p; f (f 1) * p; } printf(%.1f\n, ans); return 0; }Python 版本更简洁适合用来快速验证思路n int(input()) f g ans 0.0 for p in map(float, input().split()): ans (3 * g 3 * f 1) * p g (g 2 * f 1) * p f (f 1) * p print(f{ans:.1f})代码本身短到让人怀疑但它的推导密度很高。你能把这段代码讲明白才算真正会了这道题。3.2 为什么必须按“ans → g → f”的顺序更新很多新手写完代码后发现答案偏大十有八九是把更新顺序写反了。比如// 错误示范先更新 f再更新 g f (f 1) * p; g (g 2 * f 1) * p; ans (3 * g 3 * f 1) * p;我用一个极端简单的例子来说它错在哪。假设 n 1p 0.5。正确答案很直观只有一个位置如果是 1 就得 1^3 1 分如果是 0 就得 0 分期望是 0.5。用错误顺序手算一遍初始 f 0g 0ans 0f (0 1) * 0.5 0.5g (0 2 * 0.5 1) * 0.5 (0 1 1) * 0.5 1ans (3 * 1 3 * 0.5 1) * 0.5 (3 1.5 1) * 0.5 2.75。答案直接变成 2.75离真实的 0.5 差太远了。原因就是先更新的 f 和 g 已经把第 1 位一定为 1 的假设带进了增量计算而实际上第 1 位有 0.5 的概率是 0。正确顺序下的手算初始 f 0g 0ans 0ans (0 0 1) * 0.5 0.5g (0 0 1) * 0.5 0.5f (0 1) * 0.5 0.5。输出 0.5完美。再多看一眼 n 2、两个概率都是 0.5 的情形可以顺手验证整体逻辑。枚举 4 种结果结果连续段总分概率00无00.2501110.2510110.2511280.25期望是 (0 1 1 8) / 4 2.5。用 DP 跑一遍i 1ans 0.5g 0.5f 0.5i 2ans (3 * 0.5 3 * 0.5 1) * 0.5 2g (0.5 1 1) * 0.5 1.25f (0.5 1) * 0.5 0.75。ans 累计为 2.5和枚举一致。这种“小数据手算对照”是做期望题的保命手段。3.3 精度、读入和输出的细节题目给出的 p_i 是实数读入一定要用 doublescanf 的格式化字符串是%lf不是%d也不是%f。之前有人把概率读成整数结果整道题变成纯确定性题怎么调都不对。输出要求保留一位小数直接用printf(%.1f\n, ans)就好。这里的%f对 double 是标准写法写成%.1lf在多数环境下也能编译但没必要。浮点数方面double 的有效位数大约是 15 到 16 位十进制。本题 n 在 10^5 级别答案最大也不会超过 n^3也就是 10^15 量级double 完全扛得住输出一位小数时误差不会显现。如果哪天遇到答案超过 10^16 的变态数据可以换成 long double转移公式完全不变。注意不要因为代码里有浮点运算就随手用 float。float 只有大约 7 位有效数字在大量累加后误差会明显变大保留一位小数时可能输出错误。用 double 是最稳妥的选择。4. 从 OSU! 三次方到任意 k 次方一类题的通用解法4.1 增量公式的二项式展开P1654 的得分函数是 x^3。改一下变成 x^k整套思路依然成立因为每个位置的新增期望可以写成(L1)^k - L^k这个式子用二项式定理展开后最高只到 L^{k-1}因为 L^k 被抵消掉了。也就是说要算 k 次方得分只需要维护到“当前连续长度”的 k-1 次方期望为止。通用递推可以写成设 f_j E[L^j]则处理完第 i 个位置后fj p_i * Σ{t0}^{j} C(j, t) * f_t其中 f_0 恒等于 1。累加答案时用的是ans p_i * Σ_{j0}^{k-1} C(k, j) * f_j这里 f_j 必须用更新前的值。如果你用一个数组原地更新需要注意循环顺序从高次向低次更新。因为高次项的更新依赖低次项的旧值而低次项还没来得及被覆盖这样才不会污染。下面是一段 Python 风格的伪代码展示 k 次方得分的通用实现from math import comb def solve(p, k): f [0.0] * k f[0] 1.0 ans 0.0 for prob in p: # 先累加答案使用旧状态 inc 0.0 for j in range(k): inc comb(k, j) * f[j] ans inc * prob # 再更新各阶矩从高次到低次 for j in range(k - 1, 0, -1): val 0.0 for t in range(j 1): val comb(j, t) * f[t] f[j] val * prob return ans严格来说原地更新从高到低是安全的因为更新 f_j 时所有下标小于 j 的 f_t 都还是旧值而下标大于 j 的项已经更新完但不会被 f_j 的更新使用到。这个细节在写通用版本时尤其重要一不留神就会用上“未来状态”。4.2 不同得分规则需要维护的量平时刷题会遇到各种得分规则的变式我列一个对照表得分规则单个位置的新增公式需要维护的期望L1无或 fL^22L 1fL^33L^2 3L 1f, gL^44L^3 6L^2 4L 1f, g, h你会发现低次版本就是高次版本去掉某几项后的退化情形。先做平方版本的 OSU!再做本题最大的收益不是“会套公式”而是能直观体会到“每次得分函数升级我到底多维护了一个什么东西”。4.3 这类期望题的通用做题顺序我把这类“连续段计分 随机生成”的期望题总结成一套流程刷题时按这个顺序走基本不会跑偏写出单个位置的新增分数与当前连续长度 L 的关系delta f(L1) - f(L)展开成多项式确定需要维护哪些低阶幂次期望逐个列出这些幂次的递推公式注意乘 p_i 和清零逻辑代码里先累加答案再更新状态严格固定更新顺序拿 n 2、p 0.5 的小数据手算验证再交代码。这套流程不仅适用于 OSU! 系列很多带“连续段贡献”的期望题都能用同一个框架去解。5. 常见问题排查与调试实录5.1 用暴力枚举验证 DP 的正确性期望 DP 最怕的是推导时自我感觉良好一交上去全错。验证推导是否正确最直接的方法是写一个暴力枚举只在小 n 上跑和 DP 结果对比。下面这个 Python 函数枚举所有长度为 n 的 01 结果按概率加权求期望def brute(p): n len(p) total 0.0 for mask in range(1 n): prob 1.0 cur 0 score 0 for i in range(n): if (mask i) 1: prob * p[i] cur 1 else: prob * 1 - p[i] score cur ** 3 cur 0 score cur ** 3 total prob * score return total再用正解函数一起跑def expected(p): f g ans 0.0 for prob in p: ans (3 * g 3 * f 1) * prob g (g 2 * f 1) * prob f (f 1) * prob return ans对比brute([0.5, 0.5])和expected([0.5, 0.5])结果都应该是 2.5。我建议你随机生成 n 在 10 到 15 之间的概率数组跑几十组全部一致再放心提交。这个习惯能帮你从根上排除“公式推导错”和“代码实现错”这两类问题。5.2 高频报错点速查做题过程中我踩过和看别人踩过的坑基本可以汇总成一张表症状大概率原因处理方式答案偏大且 n 越大越离谱更新顺序错误用了更新后的 f/g 算 ans固定 ans → g → f 的顺序输出总是整数概率被读成整数或输入格式不对用 double %lf读入结果与样例相差一位小数用了 float精度不够改用 double样例能过大数据超时用了枚举或递归当正解用 O(n) 滚动变量 DP推导都对代码输出 nan某处除以 0 或读入失败检查输入是否读完概率是否有 0/1 边界边界情况也值得单独测试一遍。所有 p_i 0 时答案必然是 0所有 p_i 1 时整个序列就是一整段连续 1长度为 n答案应该是 n^3。比如 n 3、p 全为 1用 DP 跑出来应该是 27。这两个极端如果都能对上说明递推和更新顺序基本没问题。还有一个小细节输出格式只保留一位小数不要画蛇添足输出多位或者不输出。样例输出带 .0 时很多人以为答案是整数就没管结果因为格式问题 WA很冤。最后分享一点我自己的训练体会。P1654 这道题我前后见过至少三个版本平方得分、立方得分、以及把得分改成 k 次方的改编题。处理它们的套路完全一致先写增量表达式再看要维护哪些幂次期望最后严格控制更新顺序。真正动手写代码前拿 n 2、p 0.5 这种小数据手算一遍能避开绝大多数直觉错误。后来我在比赛里再遇到这类“连续段计分 概率”模型基本就是五分钟写完这就是把一道母题彻底吃透的收益。希望这篇拆解也能帮你建立同样的手感。