CF596D Wilbur and Trees 题解

原题链接

INFO 题意简述
有 棵树在一条直线上，每颗树高都为 。每棵树倒下后会带倒同方向距离小于 的树。每次随机从左右两颗树中选择一个，被砍倒的树有 的概率向左倒下， 的概率向右倒下。求最后树覆盖的期望。

不难发现任意时刻剩下来的树都是一个区间。这时候就可以从区间 dp 的角度去考虑。

我们不妨设 表示当前剩下区间 的树，在 区间内覆盖的期望长度。然而我们发现我们转移的时候外层的树向里/向外倒也会影响覆盖长度的计算。比如下面这张图：

描出来的点是树根。内层的树和外层的树可以覆盖同一片区域。因此我们需要把这个也计入状态。

考虑我们究竟在求什么。假设一个随机变量 表示区间 的期望长度。我们实际上要求的是 ，为了求出这个，我们需要用到全期望公式。

条件期望

已知 的情况下 的概率分布，此时 的期望被称作条件期望，记作 。

离散情况下的全期望公式。

其中 是关于 的函数。

要证明这个命题，我们首先根据期望的定义将 拆开：

带回原式：

利用乘法分配律外层的 放进去。

交换内外的求和号并且提出 ：

内层其实是全概率公式。其值等于 。

这就是 的期望的定义。

从含义上理解这个式子，就是通过分类讨论把 可能发生的情况枚举了一下，乘上发生的概率就是期望。

转移

我们需要通过合适的变量 来帮助我们算出来这个式子。实际上 可以取任何变量，然而既然我们希望方便转移，自然要选取一个和 有关的变量。

我们发现，一旦我们确定要砍倒某棵树了，并且其倒下的方向确定，那么它连带带到的树和覆盖的位置也是确定的，这个部分可以 预处理得出。

因此，我们不妨选取“先砍倒左侧/右侧的树和砍倒树的倒向”作为全期望公式中的 。需要注意我们要算得 本身也是一个条件概率（外层树的倒向），计算时要考虑这个条件。

首先考虑如何计算 。容易发现此时已知外层树的倒向并不会影响这个概率，因此就是 乘上树倒向某个方向的概率。

接下来我们需要计算 。对于先砍倒左侧树的情况，我们将区间分成三段：外层带倒下的部分 ，内层带到的部分 ，中间重合的部分 。利用期望的线性性质展开：

的计算是简单的，因为此时倒下的树是确定的。对于 ，实际上我们要计算这个条件概率：“在外层的树向某个方向倒下的时候的期望长度”，这构成了一个子问题，递归求解即可。

对于右侧的情况同理。

我们实际上是运用了全期望公式，把不好计算的不确定事件转化成好计算的确定性事件来求解。

错解二则

接下来说一个错误解法。

如果我们令 表示 区间内的树仍然站立，内层树（此时仍然站立的树）两端最终的倒向是 的条件期望。

转移的时候仍然枚举先砍倒哪颗树。由于我们已经确定了内层树倒下的方向，因此此时砍倒两侧概率是 。枚举内层的树倒向，分别乘上 和 进行转移。可是，这个问题的解法仍然是错误的。

这个做法依旧试图使用全期望公式来计算答案。需要计算 的概率。由于我们要求的期望是条件期望，这个概率也需要在这个条件下计算。因此我们实际上要计算的是 。需要注意，这个时候的概率变成了一个条件概率，“左树向左，右树向右”的条件会对这个概率产生影响（考虑内层的树把左侧树带倒的情况）。

此时钦定内层树倒向之后，其发生的概率也不是 和 了，而是另外一个条件概率。此时就会导致得出错误的结果。

因此，在设计概率类 dp 时需要注意这个问题。我们在设计状态的时候，计入状态的内容最好不要对未来产生影响，这个错解就是一个错误示范，因为它直接钦定了时间的结果，把概率变成了一个难以计算的条件概率。

而我们之前计入外层状态的“外层树的倒向”并不会对内层树的倒向产生影响，换言之，“外层树的倒向”和“内层先砍哪个及其倒向”是两个独立事件。

另一个值得一提的是 AndreiNet 的赛时做法 。不知道怎么过 pretests 的。

似乎他在考虑 dp 计算每一颗树最终左倒还是往右倒的概率，利用期望的线性性分到每一段，并且简单的将左侧树向右倒下和右侧树向左倒下的概率乘了起来。

实际他似乎认为相邻两棵树的倒下是独立事件（实际上并不是，左侧的树如果向左倒下，那么右侧树会“更有可能”向左倒下将左侧的树推倒）。

正确的直觉建立在正确的理解上面。如果你根本不知道自己在算什么东西就随便想当然的乱套结论，代码的正确性自然会出问题。

另外这场比赛的 pretest 这么弱吗？