隔離採礦

想法

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