題意:
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的最後一個位置。
沒有留言:
張貼留言