bzoj1657[Usaco2006 Mar]Mooo 奶牛的歌声*

bzoj1657[Usaco2006 Mar]Mooo 奶牛的歌声

题意：

n头奶牛，每头一个身高和音量。每头牛的音量会被左边离它最近的比它高的和右边离它最近的比它高的牛听到。问牛听到的最大音量。n≤50000

题解：

单调栈维护牛的身高递减。左右各做一次，累加求解。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define dec(i,j,k) for(int i=j;i>=k;i--)
 6 #define maxn 50100
 7 using namespace std;
 8 
 9 int s1[maxn],s2[maxn],h[maxn],vol[maxn],ss,n,ans[maxn];
10 inline int read(){
11     char ch=getchar(); int f=1,x=0;
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
14     return f*x;
15 }
16 int main(){
17     n=read(); inc(i,1,n)h[i]=read(),vol[i]=read();
18     s1[1]=h[1]; s2[1]=1; ss=1;
19     inc(i,2,n){while(ss&&s1[ss]<h[i])ss--; if(ss)ans[s2[ss]]+=vol[i]; s1[++ss]=h[i]; s2[ss]=i;}
20     s1[1]=h[n]; s2[1]=n; ss=1;
21     dec(i,n-1,1){while(ss&&s1[ss]<h[i])ss--; if(ss)ans[s2[ss]]+=vol[i]; s1[++ss]=h[i]; s2[ss]=i;}
22     inc(i,1,n)ans[0]=max(ans[0],ans[i]); printf("%d",ans[0]); return 0;
23 }

20160808