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\times 2\) 骨牌的概率就只与左侧连续红色格子数量有关,可以考虑 \(dp\):
\(dp_{i}:\) 对于一个 \(1\times 2\) 的无障碍空间,左侧连续红色格子数量为 \(i\),该位置可放 \(1\times 2\) 骨牌的概率。
\(init: dp_{0}= \frac{1}{4}, dp_{1}= \frac{1}{8}\)
\(trans:\)
- 前一个位置涂红:可以看作前一个位置也必须放骨牌,可以直接从 \(dp_{i-2}\) 转移。
- 前一个位置涂蓝:再前一些的位置涂色方式就无所谓了。
当然,当前空间的两个方格必须是红色。因此转移式:
预处理出 \(dp\) 数组,对于所有 \(1\times 2\) 的无障碍空间,可放置骨牌的期望就可以直接 \(O(1)\) 得到,\(2\times 1\) 的处理方式与 \(1\times 2\) 完全相同。
至此,我们就得到了所有可放置骨牌且大小为 \(2\) 的空间放骨牌最大数量的期望,再乘上总涂色方案数 \(2^{w}\) 即为答案。
code