# 39 条题解

• @ 2016-11-12 21:38:00

*****const maxn=100000;
var h,l,r:array[0..maxn+1]of longint;
var i,max,n,k:longint;
begin
while not eof do
begin
max:=0;
h[0]:=0;h[n+1]:=0;//*数据一直在变，这一次的数据可能会dai到下一次
for i:=1 to n do read(h[i]); readln;
for i:=1 to n do
begin
l[i]:=i; //k:=i-1;
while (h[i]<=h[l[i]-1])and(h[i]>0) do l[i]:=l[l[i]-1]; //***会出现和h[i]=0。。。***
end;
for i:=n downto 1 do
begin
r[i]:=i;
while (h[i]<=h[r[i]+1])and(h[i]>0) do r[i]:=r[r[i]+1];
end;
for i:=1 to n do
if (r[i]-l[i]+1)*h[i]>max then max:=(r[i]-l[i]+1)*h[i];

writeln(max);
end;
writeln('0');

end.****

• @ 2016-11-12 19:50:28

var i,j,m,n,s,t,jj,tot:longint;
a,b,f:array[0..500000] of longint;

//以一个为节点向前,向后查找,其高度大于当前值，就继续找；否则退出；
begin
while not eof do
begin
tot:=0;
fillchar(a,sizeof(a),0);
for i:=1 to n do
for i:=1 to n do
begin
j:=i; jj:=i;
while (jj>1) and (a[jj-1]>=a[i]) do dec(jj);
while (a[i]<=a[j+1]) and (j<n) do inc(j);
s:=a[i]*(j-jj+1);
if s>tot then tot:=s;
end;
writeln(tot);
end;
writeln('0');
end.

• @ 2019-03-06 01:18:17

#1 Accepted 278ms 1.387 MiB
假定一个位置为一个矩形的最小高度，以这个位置向两边扩展直到左右分别遇到第一个小于选定最小高度的数，可用单调栈，代码如下
#include <bits/stdc++.h>
using namespace std;
int n,h[100005],r[100005],l[100005],z[100005];
int main()
{
while(scanf("%d",&n)==1)
{
long long maxx=-1;
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
r[i]=i+1; l[i]=i-1;
}
int k=0;
for(int i=1;i<=n;i++)
{
while(h[z[k]]>=h[i] && k>0)
{
r[z[k]]=i;
k--;
}
l[i]=z[k];
z[++k]=i;
}
for(int i=1;i<=n;i++)
{
long long t=h[i];
t=t*(r[i]-l[i]-1);
if(t>maxx) maxx=t;
}
printf("%d\n",maxx);
}
printf("0");
return 0;
}

• @ 2017-01-25 22:04:35

玛德，就是最后输入0后面
多加了一个换行就一直TLE
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

const int N = 100000 + 5;

int n, h[N], s[N], pos[N];

int main() {
while (scanf("%d", &n) == 1) {
int top = 0;
for (int i = 1; i <= n; i++) {
while (top && h[i] <= h[s[top]]) top--;
pos[i] = s[top] + 1;
s[++top] = i;
}
top = 0; s[0] = n + 1;
int ans = 0;
for (int i = n; i >= 1; i--) {
while (top && h[i] <= h[s[top]]) top--;
ans = max(ans, (s[top] - pos[i]) * h[i]);
s[++top] = i;
}
printf("%d\n", ans);
}
printf("0");
return 0;
}

• @ 2017-01-25 22:04:53

*输出

• @ 2016-11-12 19:47:58

program fg;
var l,q,w,r,a:array[0..100000]of longint;
i,j,n,m,k,h,t,ans:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

begin
while not eof do
begin
ans:=-maxlongint;
for i:=1 to n do
h:=1;t:=1;l[1]:=1;q[1]:=1;
for i:=2 to n do
begin
while (h<=t)and(a[q[t]]>=a[i]) do
dec(t);
l[i]:=q[t];
inc(t);
q[t]:=i;
end;
h:=1;t:=1;w[1]:=n;w[0]:=n+1;
r[n]:=n;
for i:=n-1 downto 1 do
begin
while (h<=t)and(a[w[t]]>=a[i]) do dec(t);
r[i]:=w[t];
inc(t);
w[t]:=i;
end;
for i:=1 to n do
ans:=max(ans,(r[i]-l[i]-1)*a[i]);
writeln(ans);
end;
writeln(0);
end.

• @ 2014-05-06 13:56:04

• @ 2013-09-14 15:10:44

• @ 2009-11-08 16:28:13

program vj1580;

var a,l,r:array[0..100001] of longint;

n,i:longint;

max:int64;

begin

while not eof do

begin

a[0]:=-maxlongint;a[n+1]:=-maxlongint;

for i:=1 to n do

begin

l[i]:=i-1;

while a[l[i]]>=a[i] do l[i]:=l[l[i]];

end;

for i:=n downto 1 do

begin

r[i]:=i+1;

while a[r[i]]>=a[i] do r[i]:=r[r[i]];

end;

max:=0;

for i:=1 to n do

if (r[i]-l[i]-1)*a[i]>max then max:=(r[i]-l[i]-1)*a[i];

writeln(max);

end;

writeln(0);

end.

m67大牛教导我们

O（n）求每一个元素前第一个比他小的

• @ 2009-10-28 16:42:49

eof过了

楼下的真的靠的住吗

以后要相信自己了

• @ 2009-10-28 16:48:54

编译通过...

├ 测试数据 01：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：166ms

• @ 2009-10-22 16:20:45

编译通过...

├ 测试数据 01：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：88ms

莫名其妙。。。

• @ 2009-10-06 08:47:31

我跟楼下各位牛的做法不大一样啊。

我是维护了一个单调增队列。

每读入一个高度，将其插入队列中O(lgn),然后将这个点设为队尾（每个队中的点同时记录所在位置）将当前点与队中点扫一遍，记录最大值。

总计O(nlgn).

因为每次计算面积只需求每个高度到当前点的最长长度，队列相当于记录了以当前点为终点的最长递增序列。

• @ 2009-09-17 22:47:02

writeln(ans);

诡异了

这两句换一下位置就不能过？

求VIJOS评测原理！！！！

• @ 2009-10-07 18:27:19

编译通过...

├ 测试数据 01：答案正确... 586ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：586ms

模拟栈

下标栈+高度栈

当h[i]

• @ 2009-09-05 15:25:29
• @ 2009-08-26 16:46:24

告诉大家

这题会做也不一定能做对

相当神奇

• @ 2009-08-22 16:29:02

似懂非懂

还是不懂

• @ 2009-08-21 15:37:27

做了这题，得出一个重要结论：在VIJOS上用EOF是愚蠢的！

• @ 2009-08-09 00:22:18

问题解决，fammiebright现在的题解错了，从发题解。

• @ 2009-08-09 12:38:38

不就是个标准的最大子矩形嘛……

测试数据 01：运行超时|无输出...

经过本人的N+M次提交，终于明白了怎么回事：

只有 while not eof是不行的，因为最后有个空格或空行什么的。所以N会读入一个东西但不是一个数。所以读入了N还要在判断一下。

我菜啊，一开始不懂为啥这样，后来交了N次，又要来某位Ac过的大牛的代码又试了M次，终于明白了。此时本人通过率下降了2%，本题通过率下降了1%。

++++++++++++++++囧囧的分割线++++++++++++++++++

楼上说我说错了。。。大家当我啥都没说……

ID
1580

7

908

189

21%

2