CCF201612-4 压缩编码

Problem

问题描述

　　给定一段文字，已知单词a1, a2, …, an出现的频率分别t1, t2, …, tn。可以用01串给这些单词编码，即将每个单词与一个01串对应，使得任何一个单词的编码（对应的01串）不是另一个单词编码的前缀，这种编码称为前缀码。
　　使用前缀码编码一段文字是指将这段文字中的每个单词依次对应到其编码。一段文字经过前缀编码后的长度为：
　　L=a1 的编码长度 ×t1+a2 的编码长度 ×t2+…+ an 的编码长度×tn。
　　定义一个前缀编码为字典序编码，指对于1 ≤ i < n，ai的编码（对应的01串）的字典序在ai+1编码之前，即 a1, a2, …, an 的编码是按字典序升序排列的。
　　例如，文字E A E C D E B C C E C B D B E中， 5个单词A、B、C、D、E出现的频率分别为1, 3, 4, 2, 5，则一种可行的编码方案是A:000, B:001, C:01, D:10, E:11，对应的编码后的01串为1100011011011001010111010011000111，对应的长度 L 为 3×1+3×3+2×4+2×2+2×5=34。
　　在这个例子中，如果使用哈夫曼(Huffman)编码，对应的编码方案是A:000, B:01, C:10, D:001, E:11，虽然最终文字编码后的总长度只有33，但是这个编码不满足字典序编码的性质，比如C的编码的字典序不在D的编码之前。
　　在这个例子中，有些人可能会想的另一个字典序编码是A:000, B:001, C:010, D:011, E:1，编码后的文字长度为35。
　　请找出一个字典序编码，使得文字经过编码后的长度L最小。在输出时，你只需要输出最小的长度L，而不需要输出具体的方案。在上面的例子中，最小的长度L为34。

输入格式

　　输入的第一行包含一个整数n，表示单词的数量。
　　第二行包含n个整数，用空格分隔，分别表示a1, a2, …, an出现的频率，即t1, t2, …, tn。请注意a1, a2, …, an具体是什么单词并不影响本题的解，所以没有输入a1, a2, …, an。

输出格式

　　输出一个整数，表示文字经过编码后的长度L的最小值。

样例输入

5
1 3 4 2 5

样例输出

样例说明

　　这个样例就是问题描述中的例子。如果你得到了35，说明你算得有问题，请自行检查自己的算法而不要怀疑是样例输出写错了。

评测用例规模与约定

　　对于30%的评测用例，1 ≤ n ≤ 10，1 ≤ ti ≤ 20；
　　对于60%的评测用例，1 ≤ n ≤ 100，1 ≤ ti ≤ 100；
　　对于100%的评测用例，1 ≤ n ≤ 1000，1 ≤ ti ≤ 10000。

Solution

乍一眼看上去似乎跟霍夫曼编码相关，虽然题目明确了霍夫曼编码结果不一定是满足字典序的，但估计解法应该是霍夫曼编码的变形。然而还是没什么头绪，上网一搜，发现这是一个经典的dp问题——石子问题。石子问题描述为：有n堆石子，每次合并2堆，合并花费为两堆石子之和，求合成的最小花费。问题可分为三种类型：

每次任意合并两堆石子（则变成霍夫曼树构造
每次合并相邻两堆石子（通过确保只合并相邻石子确保满足字典序
每次合并相邻两堆石子，且石子环形排列（2的升级版

这里，我们只讨论第二种情况。状态转移方程如下，dp[i][j]表示合并第i堆到第j堆石子的花费（编码第i个单词到第j个单词的长度花费），sums[i]为前i堆石子（单词）的总花费。实际上是在区间i到j之间寻找一个最优的分界点，左右分别合并，再加上总体的花费。

1
2
dp[i][j]=0 #i==j
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sums[j]-sums[i-1]) #i!=j and i<=k<=j

容易分析，需要三层循环（i，j，k），时间复杂度为$O(n^3)$。提交后能有60分，显示运行超时，但这个是非Python的操作用时，估计实际考试也能过。针对这种情况，上面博文提到可以使用平行四边形优化(百科里写得很烂)，对于像上面的状态转移方程，可设 p[i][j]为区间i到j中最优的k值，则有 p[i][j-1]<=p[i][j]<=p[i+1][j] 。因此，我们可以缩小k的遍历范围，可证其复杂度降低了一个数量级，为 $O(n^2)$，修改后提交能够获得100分。

详细代码可点此