入门OJ 3792： [Noip模拟题]发射站 (单调栈)

发表于 更新于 分类于

题目

Description

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

Input

第1行：一个整数 N；

第2..N+1行：第i+1行有2个整数Hi和Vi，表示第i个发射站的高和发射的能量值。

1≤N≤800,000；1≤hi≤2,000,000,000；1≤vi≤10,000

Output

一行：一个发射站接收到的最大能量值 # 题解 单调栈不多说 ## 代码 Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
stack<int> mono_stack;
int n, H[800005], V[800005], Sum[800005], ans;
int main(int argc, char **argv) {
  scanf("%d", &n);
  for (register int i(1); i <= n; ++i) {
    scanf("%d %d", &H[i], &V[i]);
    while (!mono_stack.empty() && H[mono_stack.top()] < H[i]) 
      Sum[i] += V[mono_stack.top()], mono_stack.pop();
    if (!mono_stack.empty()) Sum[mono_stack.top()] += V[i];
    mono_stack.push(i);
  }
  for (register int i(1); i <= n; ++i) ans = max(ans, Sum[i]);
  printf("%d\n", ans);
  return 0;
}
# 其他 入门OJ 2009太坑了，又不给数据，其他网站又找不到

辣鸡大视野