#23160: 烏龜塔問題( 動態規劃 - MooreHodgson )


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [49.216.18.187]
最後登入時間 :
2024-11-10 10:25:04
e877. Q2 湖畔大樓 -- 107北市普通高中資訊學科能力競賽決賽 | From: [61.222.86.91] | 發表日期 : 2020-10-26 15:25

如題,題目要最大化動物的數量,根據貪婪法,同樣數量的動物高度總和愈低愈好。

在更新時需要考量到起點限制,所以根據起點限制低到高排序。

貪婪法:只要現在目前的高度和小於等於起點限制時直接加入。

              若不符合上述條件,則從維護高度的資料結構( PriorityQueue )中需要佔有高度最大者和目前該動物的高度選擇是否置換。

其他的練習題: c271 和 UVa 10154

 
ZeroJudge Forum