bzoj 1657: [Usaco2006 Mar]Mooo 奶牛的歌声【单调栈】

先考虑只能往一边传播，最后正反两边就行

一向右传播为例，一头牛能听到的嚎叫是他左边的牛中与高度严格小于他并且和他之间没有更高的牛，用单调递减的栈维护即可

#include<iostream>

#include<cstdio>

using namespace std;

const int N=50005;

int n,a[N],v[N],p[N],q[N],s[N],top,ans;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int main()

{

	n=read();

	for(int i=1;i<=n;i++)

		a[i]=read(),v[i]=read();

	for(int i=1;i<=n;i++)

	{

		while(top&&a[i]>a[s[top]])

			p[i]+=v[s[top--]];

		s[++top]=i;

	}

	top=0;

	for(int i=n;i>=1;i--)

	{

		while(top&&a[i]>a[s[top]])

			p[i]+=v[s[top--]];

		s[++top]=i;

	}

	for(int i=1;i<=n;i++)

		ans=max(ans,p[i]);

	printf("%d\n",ans);

	return 0;

}

巴特西

bzoj 1657: [Usaco2006 Mar]Mooo 奶牛的歌声【单调栈】

最新文章

热门文章