天天看點

01背包 ZOJ 3931 Exact Compression

題目連接配接

題意:n個數字建構哈夫曼樹,問是否存在這樣一棵樹使得:

01背包 ZOJ 3931 Exact Compression

(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-

01背包 ZOJ 3931 Exact Compression

,表示從最小的可能值到所求E的累加值E',然後對E‘進行dp

還有bitset的暴力寫法,<< 運算相當于加,參考博文

編譯人生,運作世界!

繼續閱讀