http://acm.cist.bnu.edu.cn/contest/problem_show.php?pid=1069給一些物品,虛擬幣價格v[i]=2^(ki-1),實際價值w[i].現給S個虛擬幣.要求把這些虛擬幣恰好花完,并且購得物品的實際價值總和最大.
顯然,可行的購買方案必能將所購物品分成若干組,其中每組的總價格為2^(pi-1),其中pi為S的二進制表示為1的所有位.
因此可以按位貪心,從S的最低位開始.設當前處理第k位:
1.選取剩余物品價格為2^(k-1)中價值最大的那個,如果沒有價格為2^(k-1)的物品,則表示任務無法達成.
2.將其它價格為2^(k-1)的物品,按價值從大到小排序,相鄰兩個合并成價格為2^k的物品,累積到下一階段.
這里挖掘出的貪心性質為: 一個數第k位的1,只能由不高于第k位的1合成得到.
posted on 2009-04-25 11:44
wolf5x 閱讀(220)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc