buylow.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 78 行

{
ID:maigoak1
PROG:buylow
}

program buylow;
const
  maxn=5000;
  size=10;
  digits=8;
  top=100000000;
type
  bignum=array[0..size]of longint;
var
  fin,fout:text;
  price:array[1..maxn+1]of longint;
  next:array[1..maxn]of integer;{The next day which has the same price}
  len:array[1..maxn+1]of integer;
  count:array[1..maxn+1]of bignum;
  n,i,j:integer;
  s:string;
procedure add(var a,b:bignum);
  var
    i:byte;
  begin
    if b[0]>a[0] then a[0]:=b[0];
    for i:=1 to a[0] do begin
      a[i]:=a[i]+b[i];
      if a[i]>top then begin
        a[i]:=a[i]-top;
        inc(a[i+1]);
      end;
    end;
    if a[a[0]+1]>0 then inc(a[0]);
  end;
begin
  assign(fin,'buylow.in');
  reset(fin);
  readln(fin,n);
  for i:=1 to n do
    read(fin,price[i]);
  price[n+1]:=0;
  close(fin);

  fillchar(next,sizeof(next),0);
  for i:=1 to n-1 do
    for j:=i+1 to n do
      if price[i]=price[j] then begin
        next[i]:=j;
        break;
      end;

  fillchar(count,sizeof(count),0);
  for i:=1 to n+1 do begin
    len[i]:=1;count[i][0]:=1;count[i][1]:=1;
    for j:=i-1 downto 1 do begin
      if ((next[j]=0) or (next[j]>i)) and (price[j]>price[i]) then
        if len[j]+1>len[i] then begin
          len[i]:=len[j]+1;count[i]:=count[j];
        end
        else if len[j]+1=len[i] then
          add(count[i],count[j]);
    end;
  end;

  assign(fout,'buylow.out');
  rewrite(fout);
  write(fout,len[n+1]-1,' ',count[n+1][count[n+1][0]]);
  for i:=count[n+1][0]-1 downto 1 do begin
    str(count[n+1][i],s);
    for j:=length(s)+1 to digits do
      write(fout,'0');
    write(fout,s);
  end;
  writeln(fout);
  close(fout);
end.