题目大意:

一个数列,它左边第一个比它高的人和右边第一个比它高的人要加上它的权值

思路:

单调栈维护一个单调递减的栈

正反各维护一遍

 #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);
}

最新文章

  1. armv7 armv7s arm64
  2. Android,不小心关闭了某个小窗口怎么恢复,方法介绍
  3. Lambda表达式演变
  4. Leetcode H-index
  5. struts2各个jar包的作用
  6. TCP/IP各层主要功能
  7. 零基础学Python 3之环境准备
  8. maya 操作自我整理(一)
  9. Eclipse配置JDK的源代码的src.zip
  10. springcloud(八):配置中心服务化和高可用
  11. [区块链] 密码学——Merkle 树
  12. Java 视频处理,截帧操作
  13. alpha冲刺9/10
  14. Pandas.Series.dt.dayofweek相关命令
  15. 移动端真机调试终极利器-BrowserSync(使用方法)
  16. python 历险记(二)— python 的面向对象
  17. 微信小程序两种滑动方式
  18. iOS开发-实现相机app的方法[转载自官方]
  19. fiddler常见的应用场景
  20. MVC 如何设定默认默认路由为指定的Area下的某个action(笔记)

热门文章

  1. 爬虫框架urllib 之(二) --- urllib基础
  2. configparser logging
  3. 【Codeforces 231C】To Add or Not to Add
  4. java读utf8 的txt文件,第一个字符为空或问号问题
  5. 用二分法计算a的n次幂&lt;算法分析&gt;
  6. STL map的用法介绍!
  7. 開啟活動監視器 (SQL Server Management Studio)
  8. Bone Collector II(hdu 2639)
  9. 【NOIP2016】蚯蚓(单调队列)
  10. Delphi第三方控件安装方式