chenhongbin 2009-05-18 21:29:00
点我顶贴
收藏
删除
program r460;
var n,i,j,k,k1,tot,ans:longint;
a,f:array[0..500000]of longint;
w,x:array[0..500000]of longint;
begin
readln(n);
tot:=0;
for i:=1to n do
begin
readln(a[i]);
k:=tot;
while (k>0)and(x[k]<a[i]) do dec(k);
if k=0 then
begin
f[i]:=tot;
if w[tot]<>i-1 then inc(f[i]);
tot:=1;
x[tot]:=a[i];
w[tot]:=i;
inc(ans,f[i]);
end
else
begin
if x[k]=a[i] then
begin
k1:=k;
while x[k1]=a[i] do dec(k1);
f[i]:=tot-k1+1;
end
else f[i]:=tot-k+1;
if w[tot]<>i-1 then inc(f[i]);
inc(ans,f[i]);
inc(k);
x[k]:=a[i];
w[k]:=i; tot:=k;
end;
end;
writeln(ans);
end.
大牛看一下,我只过了前面四个点,后面五个比答案大了一点点,最后一个超时