P1901 发射站

题目描述

某地有 个能量发射站排成一行，每个发射站 都有不相同的高度 ，并能向两边（两端的发射站只能向一边）同时发射能量值为 的能量，发出的能量只被两边最近的且比它高的发射站接收。显然，每个发射站发来的能量有可能被 或 或 个其他发射站所接受。

请计算出接收最多能量的发射站接收的能量是多少。

输入格式

第 行一个整数 。

第 到 行，第 行有两个整数 和 ，表示第 个发射站的高度和发射的能量值。

输出格式

输出仅一行，表示接收最多能量的发射站接收到的能量值。答案不超过 32 位带符号整数的表示范围。

输入输出样例 #1

输入 #1

3
4 2 
3 5 
6 10

输出 #1

7

说明/提示

对于 的数据，。

对于 的数据，。

对于 的数据，。

解题思路

单调栈

AC代码

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
#define lowbit(x) = ((x) & -(x))
#define rep_0(a, b, c) for (int a = b; a < c; a++)
#define rep_1(a, b, c) for (int a = b; a <= c; a++)
#define per(a, b, c) for (int a = b; a >= c; a--)
using namespace std;
struct node
{
    u64 h, v, ans = 0;
};

void solve()
{
    u64 n;
    cin >> n;
    stack<node> s;
    vector<node> v(n);
    cin >> v[0].h >> v[0].v;
    s.push(v[0]);
    i64 maxnum = 0;
    for (int i = 1; i < n; i++)
    {
        cin >> v[i].h >> v[i].v;
        if (s.top().h > v[i].h)
        {
            s.top().ans += v[i].v;
            s.push(v[i]);
        }
        else
        {
            while (!s.empty() && s.top().h < v[i].h)
            {
                v[i].ans += s.top().v;
                if (s.top().ans > maxnum)
                {
                    maxnum = s.top().ans;
                }
                s.pop();
            }
            if (!s.empty())
            {
                s.top().ans += v[i].v;
            }
            s.push(v[i]);
        }
    }

    while (!s.empty())
    {
        if (s.top().ans > maxnum)
        {
            maxnum = s.top().ans;
        }
        s.pop();
    }
    cout << maxnum << endl;
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}