题目描述
你已被气候测量协会聘用，该协会是致力于追踪全球气候在长时间内变化趋势的科学组织。 当然，这绝非易事。 他们在世界各地部署了许多小型设备，旨在对当地天气状况进行定期测量。 这些是廉价的设备，它们的功能受到某些限制。每天，它们观测一次可能会发生于当天的四类标准天气中的一种：\(Sunny\)、\(Cloudy\)、\(Rainy\) 或 \(Frogs\)。每进行 \(n\) 次观测之后，将结果报告给主服务器进行分析。但是，大量的设备导致可用的通信带宽过载。协会需要你帮忙提出一种压缩这些报告序列位数的方法。 对于一个特定的设备所处的位置，你可以假设该地每天的天气是一个独立的随机事件，并且你会得知上述四种天气发生的概率。设备的 \(4^n\) 个可能报告中的每一个都必须编码为唯一的二进制序列，满足任意序列都不是其它任意序列的前缀（重要性质，若不满足则服务器将不知道每个序列何时结束）。你的目标是使用一种编码方式，以最大减少期望的传输位数。
输入格式
第一行包含一个整数 \(n\)（\(1\le n\le 20\)） 代表每个设备进行的观测次数。
第二行包含四个正实数，\(p_{\operatorname{sunny}}\)，\(p_{\operatorname{cloudy}}\)，\(p_{\operatorname{rainy}}\) 和 \(p_{\operatorname{frogs}}\) 代表各自天气发生的概率。保证这 \(4\) 个概率小数点后不超过 \(6\) 位且和为 \(1\)。
输出格式
输出报告编码的最小期望位数，要求误差不超过 \(10^{-4}\)。
题解
设一个设备 \(4^n\) 个可能报告构成的集合 \(S\)，报告 \(x\) 的编码长度 \(l_x\)，出现概率为 \(w_x\)，则最后的期望：
\[ \sum_{x\in S}w_xl_x \]
我们不难发现这个恰好满足哈夫曼编码的代价，启发我们使用哈夫曼树来解决这类问题。
首先一个很粗糙的想法就是暴力枚举 \(4^n\) 个不同的报告序列再执行哈夫曼树算法的过程。但实际上我们注意到可以分成较少的组，满足每个组内的 \(w_x\) 的值相同。这样我们就可以用二元组 \((c,w)\) 来表示一个大小为 \(c\) 权值为 \(w\) 的组。一开始，对于一个权值形如 \(p_{\operatorname{sunny}}^ap_{\operatorname{cloudy}}^bp_{\operatorname{rainy}}^cp_{\operatorname{frogs}}^d(a+b+c+d=n)\) 的组而言，其大小为 \(\binom{n}{a\ b\ c\ d}\)。之后我们执行哈夫曼树算法的流程，每次取出堆顶的二元组 \((c,w)\) 并弹出，根据 \(c\) 的大小进行讨论： * 若 \(c=1\) 则再次取出堆顶的二元组 \((c',w')\)，将 \((1,w+w')\) 和 \((c'-1,w)\) 重新加入堆中，答案加上 \(w+w'\)。 * 若 \(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'\) 减 \(1\) 的结果，但笔者尚未清楚其中的机理。