题解

用单调栈做

#include<iostream>
#include<stack>
using namespace std;
typedef long long ll;//不开会超
const int N=1e6+5;
int n;
ll h[N],v[N],f[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i]>>v[i];
    stack<int>s;
    for(int i=1;i<=n;i++){//从左往右射能量
        while(s.size() && h[i]>h[s.top()]){//当前塔比之前的高，就能拦下
            f[i]+=v[s.top()];
            s.pop();
        }
        s.push(i);
    }
    while(s.size())s.pop();//清空
    for(int i=n;i>=1;i--){
        while(s.size() && h[i]>h[s.top()]){
            f[i]+=v[s.top()];
            s.pop();
        }
        s.push(i);
    }
    ll mx=0;
    for(int i=1;i<=n;i++)mx=max(mx,f[i]);
    cout<<mx;
    return 0;
}