{%hackmd @ioncamp/__style %}
# [隔離採礦](https://judge.tcirc.tw/ShowProblem?problemid=d088)

## 想法

- $dp[i]=dp[j]+v[i]$
- $O(n^2)$
- 維護單調 $\texttt{stack}$
- 從底到 $\texttt{top}$ 看過去是 $\texttt{decreasing}$ (非嚴格)
- 因為如果中間要隔一個比較高的勢必要被別人支配，也就不能出現在單調 $\texttt{stack}$ 的才能去取 $\texttt{max}$
- $h[i]$ 要轉移須找第一個比 $h[i]$ 還大的 $h[j]$ 能轉移的區間就是 $[1..j]$ 的 $\texttt{dp}$ 值，除了 $[1..j]$ 所形成的單調 $\texttt{stack}$ 中的 $\texttt{dp}$ 值
- 因為如果在單調 $\texttt{stack}$ 內代表他支配著他左邊的區間，也就代表是只有左邊區間內的元素能轉移
- 存在單調 $\texttt{stack}$ 內也意味著右邊的 $h$ 都比自己小
- 代表無法跟右邊的元素中間隔一個峰
- 找第一個比 $h[i]$ 還大的用另外一個單調 $\texttt{stack}$ 維護
- $O(n)$

## CODE

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;
using PQ = priority_queue<int, vector<int>, greater<int>>;
 
const int INF = 2e18;
const int maxn = 1e6 + 5;
const int M = 1e9 + 7;

int n;
int h[maxn], v[maxn], dp[maxn], dom[maxn];
int mx[maxn];

void init () {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> v[i];
}

void solve () {
    stack<int> stk;
    stack<int> stk2;

    for (int i = 1; i <= n; i++) {
        // dom[i]: h[i] 支配的區間的 dp 值 max
        // mx[i]: 從 1..i 有被支配的 index 的 dp 值取 max
        // 不能支配跟 h[i] 一樣大的, 這樣會造成 h[j] 是 [j..i] 的最大值, 中間並沒有峰
        
        while (stk.size () && h[stk.top()] < h[i]) {
            // 支配 stk.top
            dom[i] = max ({dom[i], dom[stk.top()], dp[stk.top()]});
            // 記得也要 max 到 dp[stk.top()] 因為 dom[j] 不會包含 dp[j]
            stk.pop ();
        }

        // 找上一個比 h[i] strictly greater 的
        while (stk2.size () && h[stk2.top()] <= h[i]) {
            stk2.pop ();
        }

        if (stk.empty ()) {
            dp[i] = v[i];
            mx[i] = dom[i];
        } 
        else {
            int ret = 0;
            if (stk2.size()) ret = mx[stk2.top()]; // stk2.top: 第一個比 h[i] 大的
            mx[i] = max (mx[stk.top()], dom[i]); // 大於等於他的 + 他支配的
            dp[i] = ret + v[i];
        }

        stk.push (i);
        stk2.push (i);
    }
    cout << *max_element (dp + 1, dp + n + 1) << "\n";
}
 
signed main() {
    // push stack 
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        init();
        solve();
    }
}

###### tags: `題解`