题目连接
题意:n个数字构建哈夫曼树,问是否存在这样一棵树使得:
(Fi数字大小,Ci哈夫曼表示下,'0'的数量)
分析:每次从优先队列取出两个数字可以互换位置,这样可以01互换。设a[i] <= b[i],a[i]为左儿子,b[i]为右儿子,如果加上a[i],表示累加上了a[i]下的所有点在i的位置的0的贡献,如果加上b[i]-a[i]就表示左右互换。所以可以转换为01背包问题换不换的问题,考虑到E很大,初始化为E’=E-
,表示从最小的可能值到所求E的累加值E',然后对E‘进行dp
还有bitset的暴力写法,<< 运算相当于加,参考博文
编译人生,运行世界!