#44316: C++詳解-DP


toseanlin@gmail.com (Dr. SeanXD)

學校 : 康橋雙語學校
編號 : 158065
來源 : [24.147.249.5]
最後登入時間 :
2024-12-19 10:42:57
a813. 4. 城市觀測 -- 102學年度高雄市資訊學科能力競賽複賽 | From: [24.147.249.5] | 發表日期 : 2024-11-24 12:44

本題需要使用 Long Long Int 來存資料。

宣告一個 pair<long long int, long long int> 的陣列,這個會是一個暫存區,從左到右和右到左看的原理是一樣的,以下這個暫存區簡稱為 Box。

每一次跑到一棟樓時,都要判斷 Box 裡面是否有資料,如果沒有資料就將目前的樓高度 push_back 到 Box 中,因為陣列的資料型態是 Pair,First 欄位是存樓高度,Second 欄位是存連續的時候這個高度有連續幾個。如果裡面已經有資料了就要跑一個 While 迴圈,每一次的迴圈裡要鎖定 Box 的最後一個資料,簡稱 Last。如果 Last 大於目前樓高度,就代表已經不能往前了,將 ans++ 之後就將 While 迴圈 Break 掉。如果 Last 小於目前樓高度,則將 ans += Last.second,也就是有幾個這個高度的樓棟,並且將 Box 做 pop_back。如果 Last 等於目前樓高度,則要先將 ans += Last.second,然後才將 Last.second++。並且如果 Box 中還有其他的資料就將 ans++。如果是等於的情況就不需要將目前樓高度做 push_back,其餘情況都要 push_back。

 

範例程式碼

 
ZeroJudge Forum