这个不难吧,算是常识了。。毕竟也是刷过USACO的人
对顶栈这东西前几天才遇到过,好像和在线求中位数那东西放一起了吧
单调栈倒是没什么。。。贴个代码算了。一开始有点蠢的每个位置算,后来发现出栈再算就行了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL; int a[];
int top,sta[],w[];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==)break;
for(int i=;i<=n;i++)scanf("%d",&a[i]);
a[++n]=; int top=;LL ans=;
for(int i=;i<=n;i++)
{
int L=;
while(top!=&&sta[top]>a[i])
{
L+=w[top];
ans=max(ans, (LL(L))*(LL(sta[top])) );
top--;
}
sta[++top]=a[i];w[top]=L+;
}
printf("%lld\n",ans);
}
return ;
}
poj2559
呜呜呜好困昨晚嗨皮今天早上3点才睡中午又去糜烂