Programming學習筆記: POJ 2392 Space Elevator
K種不同的磚塊，每種磚塊的高度為h，能蓋的最大高度為a，數量為c，由於安全考量，所以當現在蓋的高度超過該種磚塊的a時，就不能再用該種磚塊，求最大能蓋的高度？例如sample input，第二種磚塊的高度為23，所以如果現在建築物蓋到24以上，就只能用第一種和第三種磚塊繼續蓋。
想法：
這題要先將磚塊的a値由小到大排序，再做背包問題，算是一種greedy的方式，把a値小的磚塊盡可能放在底層，否則無法達到最大高度。
例如底下左邊這組，答案是4，如果不排序成右邊的話，算出的結果會<4。
2 2
1 4 3 2 2 1
2 2 1 1 4 3
且最後要枚舉一下dp的每個値找出最大値，因為最大値不一定位在dp的最後一個位置。
Read full article from Programming學習筆記: POJ 2392 Space Elevator
No comments:
Post a Comment