Luogu

分析

先处理左边:维护一个栈顶向栈底递增的单调栈,每次进栈则处理下面的元素;
再处理右边:反过来即可。

那么为什么可以这样呢?
对于每一个发射站,它只能影响到最左边的比它高的元素。
对于进栈时pop出去的元素,它们肯定不会比新进栈的元素高,所以可以直接舍去。
每次进栈时把能量加上,就解决了此题。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
int h[1000010],v[1000010],ans[1000010]; //输入的东西及每个能量站的收到能量 
stack<int> st; //单调栈  
void Push(int k) //单调栈进栈操作  
{
    while (!st.empty()&&h[k]>=h[st.top()]) st.pop(); //单调栈pop 
    if (!st.empty()) ans[st.top()]+=v[k]; //处理能量  
    st.push(k); //k进栈  
}
int main()
{
    int n,Ans=-1; //输入和答案  
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&h[i],&v[i]);
    for (int i=1;i<=n;i++) Push(i); //先处理左边:顺序进栈并处理  
    while (!st.empty()) st.pop(); //全部弹出  
    for (int i=n;i>=1;i--) Push(i); //再处理右边:逆序进栈并处理  
    for (int i=1;i<=n;i++) Ans=max(Ans,ans[i]); //取最大值  
    printf("%d\n",Ans); //输出  
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 07 PM