题目地址：洛谷：【P1901】发射站 – 洛谷

题目描述

某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 Hi，并能向两边（当 然两端的只能向一边）同时发射能量值为 Vi 的能量，并且发出的能量只被两边最近的且比它高的发射站接收。
显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受，特别是为了安全，每个发射站接收到的能量总和是我们很关心的问题。由于数据很多，现只需要你帮忙计算出接收最多能量的发射站接收的能量是多少。

输入输出格式

输入格式：
第 1 行：一个整数 N;
第 2 到 N+1 行：第 i+1 行有两个整数 Hi 和 Vi，表示第 i 个人发射站的高度和发射的能量值。

输出格式：
输出仅一行，表示接收最多能量的发射站接收到的能量值，答案不超过 longint。

输入输出样例

输入样例#1：

3
4 2 
3 5 
6 10

输出样例#1：

7

说明

对于 40%的数据，1<=N<=5000；1<=Hi<=100000；1<=Vi<=10000;
对于 70%的数据，1<=N<=100000；1<=Hi<=2,000,000,000；1<=Vi<=10000;
对于 100%的数据，1<=N<=1000000;1<=Hi<=2,000,000,000；1<=Vi<=10000。

题解

考虑使用单调栈，维护一个单调下降的单调栈。每次插入一个元素的时候，能接受到该发射站的信号的站一定是弹栈后的栈顶，弹栈的过程可以理解为，当前站比前面的站已经高了，因此前面的站不会收到当前站以后的发射站的信号。正着做一遍，反着做一遍，再求一遍最大值，总复杂度是[eq]O(n)[/eq]的。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1000005;

int n;
int sta[MAXN], stop = 0;
LL h[MAXN], v[MAXN], rec[MAXN];

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        h[i] = readint(); v[i] = readint();
    }
    sta[stop++] = 1;
    for(int i = 2; i <= n; i++) {
        while(stop && h[sta[stop - 1]] < h[i]) stop--;
        if(stop) rec[sta[stop - 1]] += v[i];
        sta[stop++] = i;
    }
    stop = 0;
    sta[stop++] = n;
    for(int i = n - 1; i >= 1; i--) {
        while(stop && h[sta[stop - 1]] < h[i]) stop--;
        if(stop) rec[sta[stop - 1]] += v[i];
        sta[stop++] = i;
    }
    LL mx = 0;
    for(int i = 1; i <= n; i++) {
        mx = std::max(mx, rec[i]);
    }
    printf("%lld", mx);
    return 0;
}