洛谷 P1886. 发射站

题目描述

link

分析

略

代码实现

#include <bits/stdc++.h>
using namespace std;

int n, h[1000005], v[1000005], ans[1000005];

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

    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && h[st.top()] <= h[i]) {
            ans[i] += v[st.top()];
            st.pop();
        }
        if (!st.empty()) ans[st.top()] += v[i];
        st.push(i);
    }

    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, ans[i]);
    cout << res << endl;

    return 0;
}