自动搬运

查看原文

来自洛谷，原作者为

	2022tysc0776 **

搬运于2025-08-24 22:56:15，当前版本为作者最后更新于2025-08-04 20:05:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我觉得还是很难的，但我很菜，没有发言权（

本篇题解借鉴了别的题解并融合了自己的心得。

设 $i$ 失败后从 $L_i$ 开始学习，$f_i$ 则表示从 $i$ 跳到 $i+1$ 的期望时间。

有两种情况：

1. $P_i$ 的概率，成功转移了，对期望的贡献为 $P_i$。

2. $1-P_i$ 的概率，转移失败，则从 $L_i$ 到 $i$ 都要成功转移，$i$ 才能成功转移，则贡献为 $(1-P_i)(1+\sum_{L_i \le j \le i} f_j)$。（加 $1$ 是因为转移失败也要花时间）。

$$f_i=P_i+(1-P_i)(1+\sum_{L_i \le j \le i} f_j)$$

转移不了，开始展开。

$$f_i=P_i+1-P_i+(1-P_i)\sum_{L_i \le j \le i} f_j\\ f_i-(1-P_i)f_i=1+(1-P_i)\sum_{L_i \le j <i} f_j\\ f_i=\frac{1}{P_i}+\frac{1-P_i}{P_i}\sum_{L_i\le j<i} f_j $$

然后直接 $O(n)$ 递推即可，至于 $L_i$ 的求法，用扫描线可以，用线段树也行，主播用的线段树，切记一定要下传 tag（不要问我怎么知道的 doge

然后通过观察，关于本题有一个有趣的性质：

把 $[L_i,i]$ 看成一个区间，所有区间要么不交，要么包含。

即不会出现：$L_x<L_y<x<y$

证明很显然 $L_y>L_x$ 且 $y>x$ ，所以理论上来说，$L_x$ 应该等于 $L_y$。

那我们就有一个大胆的想法，按照区间的包含关系建树，上面式子中的 $\sum_{L_i\le j<i} f_j$ 就是 $i$ 子树中不包含 $i$ 点的子树和。

建树方法可以用栈，也可以直接递归建树。递归建树的好处是可以在建树时就直接处理一些信息。

for(int i=x-1;i>=L[x];i=L[i]-1){
		ed[x].push_back(i);
		solve(i);
    //这里处理信息
}

注：有人可能会问，主播主播，有可能会出现 $L_y<y=L_x<x$ 的情况呀？

解答：是的，但是我们发现事实上，一个点连接的边的范围是 $[L_x,x-1]$，那么结合上述的证明，所有连边范围的区间必然要么包含，要么不交。（所以我们就可以开心建树了）

那我们就可以上动态 DP了。

设 $s_x$ 表示树上子树内 $f_x$ 的总和。

$$f_x=\frac{1}{P_x}+\frac{1-P_x}{P_x}\sum_{v\in son(x)} s_v\\ s_x=f_x+\sum_{v\in son(x)} s_v $$

然后建一个虚点 $n+1$，$L_{n+1}=1$，$P_{n+1}=1$。

代入一下最终答案就是 $s_{n+1}-1$。

所以去算 $f_x$ 没有意义。

$$s_x=\frac{1}{P_x}+\frac{1-P_x}{P_x}\sum_{v\in son(x)}s_v+\sum_{v\in son(x)} s_v $$

则最终转移方程为

$$s_x=\frac{1}{P_x}+\frac{1}{P_x}\sum_{v\in son(x)}s_v $$

动态 DP 部分其实就很简单了，设 $lightson(x)$ 表示 $x$ 的轻儿子集合，$hson(x)$ 表示 $x$ 的重儿子。

$$g_x=\frac{1}{P_x}+\frac{1}{P_x}\sum_{v\in lightson(x)}s_v\\ s_x=g_x+\frac{1}{P_x} s_{hson(x)} $$

矩阵就不写了，二维的矩阵自己推一下很好推出来。

目前最优解。（什么时候被超过了就来把它删掉）。