首先
[資結] [dp] [greedy]
題目在敘述上很簡單
給一個正整數 n，代表大樓的數量
n <= (1000/500,000) (easy/hard)
以及 n 個數，代表各個大樓的樓高
你可以想像成
所有大樓站一排
在這些大樓的最左側和最右側 有海
使得所有大樓 都看得到海 (可以是其中一邊或兩邊)
(如果有相同樓高的 視為看得到)
你可以砍掉一些樓層來符合上面的規則
但砍的總數要最少(可以是0)
你必須輸出 你砍完的結果
可能有多筆答案 你可以輸出任意一種
詳解:
看到hard版的 n 可以來到500,000
就知道這個問題的複雜度可以O(nlogn)甚至O(n)
而實際上還真的能O(n)
解法有很多種，以下會帶來O(n²) 和 O(n) 的解法
先從O(n²) 講解
首先，不難想到答案的形式會有個「峰」
就像 1 2 3 2 1 的 3
最左邊到峰呈遞增 峰到最右邊呈遞減
對此，我們可以枚舉每個位置當作峰
而對應的解 可以從峰開始往左
把該大樓的高度 改成跟右邊的取min
而峰右邊的部分也同理
成本你可以邊做邊求 當然你也可以依答案的總和去比
你可以存一個整數當目前最佳解的總價值(對應到成本)
還有對應的答案的數列(或單純就一個峰的索引)
如果新的解比較優就把它換掉
(會有多筆答案就代表有相同的值)
複雜度就是 O(n)枚舉 * O(n)求值 = O(n²)
重頭戲就是 O(n) 的解法了
上面的方法總有重複求解的部分
我們可以把各個峰的價值拆成 左邊+峰+右邊
一個 prefix + suffix 的概念
我們能不能把 左邊的全部一起做完 右邊的也是
最後各個峰根據它的索引值 去算它的值
最後再找出值最大的位置就行了
以左邊為例
n²的計算方法是從峰到左邊去求
而峰左邊的大樓會被更新成<=峰的高度
那如果有另一個 在現在這個峰左邊的峰
它更新到那個大樓 結果那個大樓更新的結果是一樣高的
那麼這兩個峰 從那個大樓到最左邊
這之間的結果 也會是一樣的
對此 如果我們要優化解法
左邊的部分 應該也從左邊開始去做前綴
接下來就不再去做發想了
直接上解法
我們開一個大小為 n 的陣列 left
代表以 i 為峰
從左邊部分的解的總值(包含峰)
而峰的總值也就是 left[i] + right[i] - height[i]
- height[i] 因為左和右都包含峰 所以要減掉一個
我們先寫出一部份的 dp式
left[i] = left[j] + (i - j)*height[i]
其中 j 代表
i往左找 第一個比<=height[i] 的位置
left[0] = height[0]
對於海景第一排的 A 而言
當然想多高就多高
對於 B 點
B比A還高 那就直接繼承A的值就行了
那對於 C 呢
C 所對應的 j 是跟他一樣的A
而這之間的樓層 必須改為C的值
也就是 + (i - j)*height[i]
D因為是最低點
所以從最左邊到自己 這段全部弄成平的
E 繼承 D，同 B繼承A一樣
這部分衍生一個新的問題
要如何找出所有位置的 j 點呢?
如果每個位置都往左一直找
如果是遞減數列
這樣就要比較 1+2+...+n = O(n²)
我們可以用一個聽說叫 單調隊列 的東西
(只是這個不用彈出隊頭元素)
我們可以根據一個原則
C比A更靠近D，而且C<=A
所以C完全可以取代掉A
你可以算一下複雜度
我算 最差應該只要做 2n次 比較就行了
我們建個 stack 裡面裝索引
一開始裡面放 [A]
維持裡面元素對應的 height 是嚴格遞增的
而存放的索引值是由左到右 也是嚴格遞增
新加入的值每次都跟stack.top 比
比較大就直接加入 同B繼承A一樣
stacke 變成 [A, B]
現在加入C， C比B小
那我們就把B拔掉，繼續比
A 跟 C 一樣，這邊我們要求要嚴格 所以A也拔掉
所以 C 其實同 D 一樣，從左到C直接打平
stack 被拔到空的後 又把C放進去
於是 stack 變成 [C]
附上一段程式碼
left = [0]*n
left[0] = height[0]
stack = [0] # strictly increasing
for i in range(1, n):
while stack and height[i] <= height[stack[-1]]:
stack.pop()
if stack:
j = stack[-1] # inherit j
left[i] = left[j] + (i - j)*height[i]
else:
left[i] = height[i] * (i + 1)
stack.append(i)
右邊同理 只是索引上反過來
從右到左做而已
stack 一樣是根據 height 遞增
存放的索引變成遞減
最後就用上面的算式 left[i] + right[i] - height[i]
去算各個峰值的總價值 求出最大的峰的索引
(python 這部分可以一行寫 真香)
然後求出峰值再用上面提到的方法
生出大樓的高度就大功告成了
總結一下
線性求前綴，其中有使用單調隊列
但是這部分的複雜度是總共O(n)
是用+的 不是*的
後綴同理
最後得到峰值 轉成答案
複雜度是令人意外的O(n)
以上是綠牌發言
歡迎大家留言指教
(我是蠻想知道到底什麼人會來看我小屋文的= =)
創作內容
cf #622 (Div. 2) pC Skyscrapers
未分類 (17)