Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴代码,您自己看

Posted by zhougelin at 2005-08-17 19:36:51 on Problem 2559
In Reply To:这个预处理怎么做?能 n 么 Posted by:sunmoonstar_love at 2005-08-17 19:33:50
{$R-,Q-,S-,I-}
program pku2559;
const inputfilename='';
      outputfilename='';
      maxn=100005;
var n,top:longint;
    answer:int64;
    height,left,right,stack:array[0..maxn]of longint;
    buf:array[0..1 shl 18]of byte;
function read_data:boolean;
var i:longint;
begin
      read(n);
      if n=0 then read_data:=false else
      begin
        read_data:=true;
        for i:=1 to n do
           read(height[i]);
        readln;
      end;
end;
procedure main;
var i:longint;
    tmp:int64;
begin
       height[0]:=-1;height[n+1]:=-1;
       top:=1;stack[1]:=0;
       for i:=1 to n do
       begin
          while height[i]<=height[stack[top]] do top:=top-1;
          left[i]:=stack[top]+1;
          top:=top+1;
          stack[top]:=i;
       end;
       top:=1;stack[1]:=n+1;
       for i:=n downto 1 do
       begin
          while height[i]<=height[stack[top]] do top:=top-1;
          right[i]:=stack[top]-1;
          top:=top+1;
          stack[top]:=i;
       end;
       answer:=0;
       for i:=1 to n do
       begin
          tmp:=int64(right[i]-left[i]+1)*int64(height[i]);
          if answer<tmp then answer:=tmp;
       end;
       writeln(answer);
end;
begin
      assign(input,inputfilename);
      settextbuf(input,buf);
      reset(input);
      assign(output,outputfilename);
      rewrite(output);
      while read_data do
        main;
      close(input);
      close(output);
end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator