Download presentation
Presentation is loading. Please wait.
1
11908: Skyscraper ★★★☆☆ 題組：Problem Set Archive with Online Judge
解題者：陳冠智 解題日期：2018年5月31日 題意：大樓要廣告出租，有𝑁個廣告(1≤𝑁≤30000)，每個廣告給定起始樓層𝐴(1≤𝐴≤ 10 5 )，占用樓層數𝐵(1≤𝐵≤ 10 5 )與廣告收益𝐶(1≤𝐶≤1000 )。若同一層只能放一個廣告，求廣告的最大收益。
2
題意範例： 3 1 5 1 (N=3，有3個廣告) 2 10 3 7 12 1 (從1F開始5層，收益1) (從2F開始10層，收益3)
18 1 17 16 15 14 13 12 11 3 10 9 8 7 6 5 4 2 0F 樓 N0 N1 N2 題意範例： 3 1 5 1 2 10 3 7 12 1 output: 3 (N=3，有3個廣告) (從1F開始5層，收益1) (從2F開始10層，收益3) (從7F開始12層，收益1) (只選擇廣告N1，收益3最高)
3
12 5 6 11 10 9 8 4 7 3 2 1 樓 N0 N1 N2 N3 N4 5 0 2 4 6 7 5 4 2 8 7 6 6 7 2 4 output: 18 (N=5，有5個廣告) (從0F開始2層，收益4) (從6F開始7層，收益5) (從4F開始2層，收益8) (從7F開始6層，收益6) (從7F開始2層，收益4) (選擇廣告N0+N2+N3， 收益4+8+6 = 18最高)
4
用DP陣列trace每一層樓最高收益的廣告選擇 (當遇到某廣告結束樓層，判斷加入該廣告與否) 𝑠𝑡𝑎𝑟𝑡 𝑒𝑛𝑑 𝑣𝑎𝑙𝑢𝑒
解法： 紀錄每個廣告的起始樓層, 結束樓層與收益值 將所有廣告以結束樓層排序 用DP陣列trace每一層樓最高收益的廣告選擇 (當遇到某廣告結束樓層，判斷加入該廣告與否) 𝑠𝑡𝑎𝑟𝑡 𝑒𝑛𝑑 𝑣𝑎𝑙𝑢𝑒 DP公式: 𝑝𝑟𝑜𝑓𝑖𝑡[𝑓] = 𝑀𝑎𝑥 (𝑝𝑟𝑜𝑓𝑖𝑡 𝑓−1 ,𝑝𝑟𝑜𝑓𝑖𝑡 𝑓 ,𝑝𝑟𝑜𝑓𝑖𝑡 𝑁 𝑖 .𝑠𝑡𝑎𝑟𝑡−1 + 𝑁 𝑖 .𝑣𝑎𝑙𝑢𝑒)
5
解法範例： 0 2 4 6 7 5 4 2 8 7 6 6 7 2 4 start end value N0 1 4 N1 5 8 N2 7
12 6 5 18 11 16 10 9 8 4 7 3 2 1 樓 N0 N1 N2 N3 N4 profit start end value 1 4 6 12 5 8 7 sort by end 廣告 start end value N0 1 4 N1 5 8 N2 7 N3 12 6 N4
Similar presentations
