Bzoj 1657: [Usaco2006 Mar]Mooo 奶牛的歌声 单调栈
1657: [Usaco2006 Mar]Mooo 奶牛的歌声
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 631 Solved: 445
[Submit][Status][Discuss]
Description
Farmer John's N (1 <= N <= 50,000) cows are standing in a very straight row and mooing. Each cow has a unique height h in the range 1..2,000,000,000 nanometers (FJ really is a stickler for precision). Each cow moos at some volume v in the range 1..10,000. This "moo" travels across the row of cows in both directions (except for the end cows, obviously). Curiously, it is heard only by the closest cow in each direction whose height is strictly larger than that of the mooing cow (so each moo will be heard by 0, 1 or 2 other cows, depending on not whether or taller cows exist to the mooing cow's right or left). The total moo volume heard by given cow is the sum of all the moo volumes v for all cows whose mooing reaches the cow. Since some (presumably taller) cows might be subjected to a very large moo volume, FJ wants to buy earmuffs for the cow whose hearing is most threatened. Please compute the loudest moo volume heard by any cow.
Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。每头奶牛有一个确定的高度h(1<=h<=2000000000),叫的音量为v (1<=v<=10000)。每头奶牛的叫声向两端传播,但在每个方向都只会被身高严格大于它的最近的一头奶牛听到,所以每个叫声都只会 被0,1,2头奶牛听到(这取决于它的两边有没有比它高的奶牛)。 一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后,Farmer John打算买一个耳罩给被残害得最厉 害的奶牛,请你帮他计算最大的总音量。
Input
* Line 1: A single integer, N.
* Lines 2..N+1: Line i+1 contains two space-separated integers, h and v, for the cow standing at location i.
第1行:一个正整数N.
第2到N+1行:每行包括2个用空格隔开的整数,分别代表站在队伍中第i个位置的奶牛的身高以及她唱歌时的音量.
Output
* Line 1: The loudest moo volume heard by any single cow.
队伍中的奶牛所能听到的最高的总音量.
Sample Input
4 2
3 5
6 10
INPUT DETAILS:
Three cows: the first one has height 4 and moos with volume 2, etc.
Sample Output
HINT
队伍中的第3头奶牛可以听到第1头和第2头奶牛的歌声,于是她能听到的总音量为2+5=7.虽然她唱歌时的音量为10,但并没有奶牛可以听见她的歌声.
Source
题解:
单调栈。
正反各做一遍即可。。。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 50010
int h[MAXN],v[MAXN],H[MAXN],V[MAXN],a[MAXN];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
int main()
{
int n,i,top,MX;
n=read();
for(i=;i<=n;i++)h[i]=read(),v[i]=read();
top=;
memset(a,,sizeof(a));
for(i=;i<=n;i++)
{
if(h[i]<=H[top])H[++top]=h[i],V[top]=v[i];
else
{
while(top>&&h[i]>H[top]){a[i]+=V[top--];}
H[++top]=h[i];V[top]=v[i];
}
}
top=;
memset(H,,sizeof(H));
memset(V,,sizeof(V));
for(i=n;i>=;i--)
{
if(h[i]<=H[top])H[++top]=h[i],V[top]=v[i];
else
{
while(top>&&h[i]>H[top]){a[i]+=V[top--];}
H[++top]=h[i];V[top]=v[i];
}
}
MX=-;
for(i=;i<=n;i++)MX=max(MX,a[i]);
printf("%d",MX);
return ;
}
最新文章
- vi 常用命令
- selenium grid中的多个线程同步执行
- linux笔记十----虚拟机网络配置
- nginx环境下配置nagios-关于nagios配置文件nginx.conf
- 简单的线程同步问题:两个线程交替执行N次【Synchronized、Lock、ArrayBlockingQueue】
- Java实现mysql数据库备份
- iOS UIKit:Auto Layout
- POI操作Excel2007实例二之“SXSSFWorkbook”处理海量数据
- 统计图表类库--libchart使用简介
- 【百度地图API】如何进行地址解析与反地址解析?——模糊地址能搜索到精确地理信息!
- Git 删除文件
- 算法模板——线段树6(二维线段树:区域加法+区域求和)(求助phile)
- 无格式转换php
- 基于角色的访问控制 (RBAC)权限管理
- 【学习总结】GirlsInAI ML-diary day-1-初识Python-Anaconda-Jupyter
- 【运维】略谈Raid级别
- POST 上传 JSON 数据
- SHELL调用存储过程
- 前端-CSS-5-继承性&;层叠性&;权重比较
- Redis.RedisNativeClient的方法get_Db 没有实现