edu 107 E（概率期望, dp）

edu 107 E

一道很具有启发意义的概率期望题，需要从期望的本质来思考。

题目要求计算所有 \(2^{w}\) 种涂色方式可放多米诺骨牌的最大数量总和。按照常规想法思考是很困难的，需要换个角度：考虑每个可放置骨牌的 \(1\times 2(2\times 1)\) 长条格对答案贡献的期望。但是每个这样的长条格的摆放会受其他长条格的影响（与其不同的长条格可能会占据该长条格的部分空间），需要考虑容斥。

假定钦定好了一种涂色方式，那么显然红蓝两种颜色是不会互相干扰的，因为红色方格只能横着放，蓝色方格只能竖着放。于是，\(1\times 2\) 的长条格可以按每一行考虑，\(2\times 1\) 的长条格可以按每一列考虑，二者对答案的贡献也可以分别计算并求和，因为不会相互影响。

为了方便表述，现在只考虑 \(1\times 2\) 长条格的情况。对于一种固定的涂色方式，现在考虑贪心地放置 \(1\times 2\) 的长条格：对于每个包含连续红色方格的水平段，钦定从左端点开始依次放置，直到放不下。显然这样贪心是对的，可以最大化 \(1\times 2\) 长条格放置的数量。那么，对于 \(\forall 1\times 2\) 的无障碍空间，可以放置 \(1\times 2\) 长条格的条件：

1. 两个方格均涂成红色
2. 该位置左侧的连续红色格子数必须是偶数（因为已经钦定必须按上述贪心方式摆放）

那么，每个这样的位置可放置 \(1\times 2\) 骨牌的概率就只与左侧连续红色格子数量有关，可以考虑 \(dp\)：

\(dp_{i}:\) 对于一个 \(1\times 2\) 的无障碍空间，左侧连续红色格子数量为 \(i\)，该位置可放 \(1\times 2\) 骨牌的概率。

\(init: dp_{0}= \frac{1}{4}, dp_{1}= \frac{1}{8}\)
\(trans:\)

1. 前一个位置涂红：可以看作前一个位置也必须放骨牌，可以直接从 \(dp_{i-2}\) 转移。
2. 前一个位置涂蓝：再前一些的位置涂色方式就无所谓了。

当然，当前空间的两个方格必须是红色。因此转移式：

\[dp_{i} = \frac{1}{4} \times (dp_{i-2} + \frac{1}{2}) \]

预处理出 \(dp\) 数组，对于所有 \(1\times 2\) 的无障碍空间，可放置骨牌的期望就可以直接 \(O(1)\) 得到，\(2\times 1\) 的处理方式与 \(1\times 2\) 完全相同。

至此，我们就得到了所有可放置骨牌且大小为 \(2\) 的空间放骨牌最大数量的期望，再乘上总涂色方案数 \(2^{w}\) 即为答案。

code