题解：P10256 高仿的 Migos

· · 题解

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

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

设 i 失败后从 L_i 开始学习，f_i 则表示从 i 跳到 i+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)}

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

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