533_1000

给出n个频率freq[n]，用{"pi", "ka", "chu"}构造n个单词work[n]，使得任意一个单词不是另一个单词的前缀，求work[0] * freq[0] + work[1] * freq[1] + ...的最小值，及其方法数。

 

用{"pi", "ka", "chu"}(2, 2, 3)构造一个字典树，联系哈弗曼编码，将freq降序排列，则长的先构造。

由于任意一个单词不是另一个单词的前缀，所以单词都再叶子结点上。

dp状态为(deep, k, t1, t2, t3) 表示已处理完深度至deep的结点，构造了k个单词，

深度为k + 1的叶子结点有t1个，

深度为k + 2的叶子结点有t2个，

深度为k + 3的叶子结点有t3个，

因为使用的元素长度最长为3，使得这个状态设计成为可能。

统计的时候注意freq值一样是等价的，要用到组合数。。