a219.
Q_6_24 隔離採礦 (@@@)(108 全國高中賽)
Content
外星採礦隊在烏邦圖星球已經探勘到某種礦物的礦脈，這條礦脈是一個筆直的直線， 且一共有 n 個可以挖礦井的地點，這些地點就稱為可開採點。所有的可開採點由 1 到 n 依序編號，第 i 個可開採點的高度為 h(i) 而開採價值為 v(i)。 現在希望能找出某些可開採點來實際進行鑽井挖礦，因為安全因素，任兩個礦井之間 必須有另外一個開採點，其高度超過這兩個礦井。身為外星採礦隊的程式設計師，你 的目標是計算出最大的開採價值總和。 下圖是一個 n =10 的例子，圖中各點的高度為 y 軸座標，而開採價值則標註於各點 旁邊。如圖所示，各點的高度依序是 h = (2, 5, 3, 2, 4, 2, 3, 1, 4, 3)， 而開採價值則依序是 v = (1, 8, 3, 1, 5, 1, 4, 2, 4, 2)，也就是說 h(1)=2, h(2)=5, …, h(10)=3，而 v(1)=1, v(2)=8, …, v(10)=2。在此例中，最佳的開採方式是圖中被圓圈所圈起來的四個點，所能獲得的最大開採價值總 和為 1+3+4+2=10。你可以看到，任兩個實際開採點之間都有一個高度更高的點。
Input
每筆測資的第一行是一個正整數 n， n 1e6，代表可開採點的數量。 第二行是 n 個非負整數，依序代表每一點的高度 h(1), h(2), …, h(n)；第三行 是 n 個正整數，依序代表每一點的開採價值 v(1), v(2), …, v(n)。每一行相鄰 數字間以一空白間隔。每一點的高度不會超過 1e9，價值不會超過 1e5。
Output
輸出爲一整數，代表最大的開採價值總和。每筆測資的答案不超過 2e9。
Sample Input
#1
10 2 5 3 2 4 2 3 1 4 3 1 8 3 1 5 1 4 2 4 2
Sample Output
#1
10
Sample Input
#2
5 3 3 3 3 3 5 3 2 3 4
Sample Output
#2
5
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (20%): 1.0s , <50M
公開 測資點#1 (20%): 1.0s , <50M
公開 測資點#2 (20%): 1.0s , <50M
公開 測資點#3 (20%): 1.0s , <50M
公開 測資點#4 (20%): 1.0s , <50M
公開 測資點#0 (20%): 1.0s , <50M
公開 測資點#1 (20%): 1.0s , <50M
公開 測資點#2 (20%): 1.0s , <50M
公開 測資點#3 (20%): 1.0s , <50M
公開 測資點#4 (20%): 1.0s , <50M
Hint ：
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||