luogu 1901 发射站
2024-09-28 08:41:33
题目大意:
一个数列,它左边第一个比它高的人和右边第一个比它高的人要加上它的权值
思路:
单调栈维护一个单调递减的栈
正反各维护一遍
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#define ll long long
#define inf 2147383611
#define MAXN 1001001
using namespace std;
inline ll read()
{
ll x=,f=;
char ch;ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,a[MAXN],v[MAXN],st[MAXN],top,ans[MAXN],maxn;
int main()
{
n=read();
for(int i=;i<=n;i++) a[i]=read(),v[i]=read();
for(int i=;i<=n;i++)
{
while(top&&a[st[top]]<=a[i]) top--;
ans[st[top]]+=v[i];
st[++top]=i;
}
top=;
for(int i=n;i>=;i--)
{
while(top&&a[st[top]]<=a[i]) top--;
ans[st[top]]+=v[i];
st[++top]=i;
}
for(int i=;i<=n;i++) maxn=max(maxn,ans[i]);
printf("%d",maxn);
}
最新文章
- armv7 armv7s arm64
- Android,不小心关闭了某个小窗口怎么恢复,方法介绍
- Lambda表达式演变
- Leetcode H-index
- struts2各个jar包的作用
- TCP/IP各层主要功能
- 零基础学Python 3之环境准备
- maya 操作自我整理(一)
- Eclipse配置JDK的源代码的src.zip
- springcloud(八):配置中心服务化和高可用
- [区块链] 密码学——Merkle 树
- Java 视频处理,截帧操作
- alpha冲刺9/10
- Pandas.Series.dt.dayofweek相关命令
- 移动端真机调试终极利器-BrowserSync(使用方法)
- python 历险记(二)— python 的面向对象
- 微信小程序两种滑动方式
- iOS开发-实现相机app的方法[转载自官方]
- fiddler常见的应用场景
- MVC 如何设定默认默认路由为指定的Area下的某个action(笔记)