[WF2015L]Weather Report

题目描述

你已被气候测量协会聘用，该协会是致力于追踪全球气候在长时间内变化趋势的科学组织。 当然，这绝非易事。 他们在世界各地部署了许多小型设备，旨在对当地天气状况进行定期测量。 这些是廉价的设备，它们的功能受到某些限制。每天，它们观测一次可能会发生于当天的四类标准天气中的一种：$Sunny$、$Cloudy$、$Rainy$ 或 $Frogs$。每进行 $n$ 次观测之后，将结果报告给主服务器进行分析。但是，大量的设备导致可用的通信带宽过载。协会需要你帮忙提出一种压缩这些报告序列位数的方法。 对于一个特定的设备所处的位置，你可以假设该地每天的天气是一个独立的随机事件，并且你会得知上述四种天气发生的概率。设备的 $4^n$ 个可能报告中的每一个都必须编码为唯一的二进制序列，满足任意序列都不是其它任意序列的前缀（重要性质，若不满足则服务器将不知道每个序列何时结束）。你的目标是使用一种编码方式，以最大减少期望的传输位数。

输入格式

第一行包含一个整数 $n$（$1\le n\le 20$） 代表每个设备进行的观测次数。

第二行包含四个正实数，$p_{\mathrm{sunny}}$，$p_{\mathrm{cloudy}}$，$p_{\mathrm{rainy}}$ 和 $p_{\mathrm{frogs}}$ 代表各自天气发生的概率。保证这 $4$ 个概率小数点后不超过 $6$ 位且和为 $1$。

输出格式

输出报告编码的最小期望位数，要求误差不超过 ${10}^{-4}$。

题解

设一个设备 $4^n$ 个可能报告构成的集合 $S$，报告 $x$ 的编码长度 $l_x$，出现概率为 $w_x$，则最后的期望：

$$\sum _{x\in S}{w}_x{l}_x$$

我们不难发现这个恰好满足哈夫曼编码的代价，启发我们使用哈夫曼树来解决这类问题。

首先一个很粗糙的想法就是暴力枚举 $4^n$ 个不同的报告序列再执行哈夫曼树算法的过程。但实际上我们注意到可以分成较少的组，满足每个组内的 $w_x$ 的值相同。这样我们就可以用二元组 $(c,w)$ 来表示一个大小为 $c$ 权值为 $w$ 的组。一开始，对于一个权值形如 $p_{\mathrm{sunny}}^a{p}_{\mathrm{cloudy}}^b{p}_{\mathrm{rainy}}^c{p}_{\mathrm{frogs}}^d(a+b+c+d=n)$ 的组而言，其大小为 $(\genfrac{}{}{0ex}{}{n}{abcd})$。之后我们执行哈夫曼树算法的流程，每次取出堆顶的二元组 $(c,w)$ 并弹出，根据 $c$ 的大小进行讨论： * 若 $c=1$ 则再次取出堆顶的二元组 $(c^{\prime },w^{\prime })$，将 $(1,w+w^{\prime })$ 和 $(c^{\prime }-1,w)$ 重新加入堆中，答案加上 $w+w^{\prime }$。 * 若 $c>1$ 且 $c$ 为奇数，则将 $(\frac{c-1}{2},2w)$ 和 $(1,w)$ 加入堆中，答案加上 $2w$。 * 若 $c>0$ 且 $c$ 为偶数，则将 $(\frac{c}{2},2w)$ 加入堆中，答案加上 $2w$。

重复上述步骤直到堆中只有一个二元组，且该二元组大小为 $1$。

时间复杂度限于笔者能力，不能给出一个精确的计算，只能给出一个粗略的上下界。首先一开始初始的二元组个数为 $O(n^3)$，上界即通过假定每个二元组中 $c$ 的 $\log n!$ 个二进制位都取 $1$ 得到，此时堆中最多会有 $O(n^3\log n!)$ 即 $O(n^4\log n)$ 个二元组，那么复杂度上界为 $O(n^4\log n\log (n^4\log n))$ 即 $O(n^4{\log }^{2}n)$ 级别；下界为假设每次都恰好使当前方案数总和减半，那么复杂度为 $O(n^3\log 4^n\log n^4)$ 即 $O(n^4\log n)$ 级别，若有读者知道如何精确分析上下界欢迎与笔者讨论。

通过实际的检验，在题目数据范围内该算法的实际运行与上面估计有较好的拟合，但若出现概率为 $0$ 的情况（在数据范围外），则会呈现明显高于上文估计的上界的增长，这大概是由于上述分析忽略情况 $1$ 对 $c^{\prime }$ 减 $1$ 的结果，但笔者尚未清楚其中的机理。