網頁

2014年4月30日 星期三

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的最後一個位置。


沒有留言:

張貼留言