PVOI14_4 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

Uses    math;
const   fi      ='';
        fo      ='';
        maxN    =5*trunc(1e4)+1;
 
type    arr1    =array[0..maxN] of longint;
        arr2    =array[0..maxN,1..4] of longint;
 
var     n       :longint;
        a       :arr1;
        T       :arr2;
        cs      :arr1;
        f       :arr2;
procedure QS(var a,cs:arr1;l,r:longint);
var     i,j,x,tg        :longint;
begin
        i:=l;j:=r;
        x:=a[l+random(r-l+1)];
        repeat
                while a[i]<x do inc(i);
                while a[j]>x do dec(j);
                if i<=j then
                begin
                        tg:=a[i];a[i]:=a[j];a[j]:=tg;
                        tg:=cs[i];cs[i]:=cs[j];cs[j]:=tg;
                        inc(i);
                        dec(j);
                end;
        until i>j;
        if l<j then QS(a,cs,l,j);
        if i<r then QS(a,cs,i,r);
end;
 
Procedure Update(x,k,v:longint);
begin
        while x<=maxN do
        begin
                T[x,k]:=max(T[x,k],v);
                x:=x+x and (-x);
        end;
end;
 
function Get(x,k:longint):longint;
begin
        Get:=0;
        while x>0 do
        begin
                Get:=Max(Get,t[x,k]);
                x:=x-x and (-x);
        end;
end;
 
procedure xuly;
var     i, j    :longint;
        a2 :arr1;
        dem     :longint;
        max_h   :longint;
        tmp     :longint;
        ans     :longint;
begin
        for i:=1 to n do a2[i]:=a[i];
        fillchar(t,sizeof(t),0);
        QS(a2,cs,1,n);
        dem:=1;
        a[cs[1]]:=dem;
        for i:=2 to n do
                begin
                        if a2[i]>a2[i-1] then inc(dem);
                        a[cs[i]]:=dem;
                end;
        //for i:=1 to n do write(a2[i],' ');writeln;
        max_h:=dem;
        ///// 1
        for i:=1 to n do
                begin
                        f[i,1]:=Get(a[i]-1,1)+1;
                        Update(a[i],1,f[i,1]);
                end;
        ///2
        for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],2)+1;
                        if tmp<=2 then tmp:=0;
                        begin
                                f[i,2]:=tmp;
                                Update(max_h-a[i]+1,2,max(f[i,1],f[i,2]));
                        end;
                end;
       // writeln(f[5,2]);
        ///3
         for i:=1 to n do
                begin
                        tmp:=Get(a[i]-1,3)+1;
                        if tmp<=3 then tmp:=0;
 
                        begin
                                f[i,3]:=tmp;
                                Update(a[i],3,max(f[i,2],f[i,3]));
                        end;
                end;
         //writeln(f[11,3]);
         //4
          for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],4)+1;
                        if tmp<=4 then tmp:=0;
 
                        begin
                                f[i,4]:=tmp;
                                Update(max_h-a[i]+1,4,max(f[i,3],f[i,4]));
                        end;
                end;
         // writeln(f[14,4]);
          ans:=0;
          for i:=1 to n do ans:=max(ans,f[i,4]);
          writeln(ans);
end;
procedure run;
var     i :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                begin
                        read(a[i]);
                        cs[i]:=i;
                end;
        xuly;
        close(input);close(output);
end;
 
begin
        run;
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*