题解 P1901 【发射站】

· · 题解

这道题和洛谷里这道题 P1823 十分相似。
做完这道题之后可以去做上面那道题。算是一个加强版吧。
这道题题意还是很明显的，我们维护一个单调栈即可。我们维护栈中的发射站高度的单调性。
栈中储存发射站的标号。我们将接收能量的过程分成两个阶段：
1.入栈时，由于栈是具有单调性的，如果栈顶的元素没有新加进来的元素高，那么他肯定就不能给后面的元素传输能量了，我们退掉这个元素，将新的元素加进来即可。
2.新的元素加进来以后，会对他在栈中下面那个元素传输能量，也就是离他最近还高于他的那个。P.S.（不需要对栈空时进行特判，我们只是对0这个元素传输了能量而已，最后不统计就行了）

那么确定思路以后，我们算法流程就是
for{
读入新元素
while(栈非空&&新元素高度大于栈顶元素高度)新元素能量加上栈顶元素能量，退栈； 栈顶元素能量加上新元素能量（对应第二种情况）
将新元素加入栈中
}
扫一遍传输能量的数组，找到max输出即可。

代码如下，就不加注释了，上面解释的很清楚了（很短吧）：

 #include<iostream>
using namespace std;
const int maxn=1e6+10;
int s1[maxn],h[maxn],v[maxn],sum[maxn],ans,n,top;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i]>>v[i];
        while(top&&h[s1[top]]<h[i])sum[i]+=v[s1[top--]];
        sum[s1[top]]+=v[i];
        s1[++top]=i;
    }
    for(int i=1;i<=n;i++)ans=max(ans,sum[i]);
    cout<<ans;
    return 0;
}