洛谷:P1901 发射站

(Updated: )
OI
views
Word count: 395 (~1 mins to read) Last updated:

原题地址:https://www.luogu.org/problemnew/show/P1901

题目简述

有 N 个能量发射站排成一行，每个都有**不相同的高度 $H_i$**，能向两边（当然两端的只能向一边）同时发射能量值为$V_i$ 的能量，并且发出的能量只被两边最近的且比它高的发射站接收。

显然，每个发射站发来的能量有可能被0或1或2个其他发射站所接受，求接收最多能量的发射站接收的能量是多少。

思路

每个能量塔射出的能量被左右第一个比其高的塔所拦截。隐隐约约觉得可以用单调栈搞……
维护一个高度单调不升栈，考虑依次将能量塔i加入栈：

  1. 如果高度比栈顶元素大或栈空，栈顶元素能量加上$V_i$，压入栈;
  2. 如果高度比栈顶元素小（栈顶元素编号记为top），当前能量塔i接收的能量加上$V_{top}$，弹出栈顶元素。重复执行直到符合情况1，按1的处理方法处理。
    最后直接扫描一遍最大值，输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int s1[1000010],h[1000010],v[1000010],sum[1000010],ans,n,top;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&h[i],&v[i]);
        while(top&&h[s1[top]]<h[i])
            sum[i]+=v[s1[top]],top--;
        sum[s1[top]]+=v[i];
        top++;
        s1[top]=i;
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,sum[i]);
    printf("%d",ans);
    return 0;
}