VODIVIDE – SPOJ

Đề bài:

Thuật toán:

Bài này có thể giải bằng phương pháp Quy hoạch động hoặc CTDL Heap. Ở đây giải theo phương pháp Quy hoạch động.

  • Gọi F[i,j] là tổng số tiền lớn nhất mà Sơn nhận được khi xét i đồng và Sơn được j đồng
  • F[i,j]:=max(F[i-1,j],F[i-1,j-1]+b[i]);

Code:

uses    math;
const   fi='';
        fo='';
        maxn=5000+2;
var     f:array[0..maxn,0..maxn] of longint;
        a,b,cs:array[1..maxn] of longint;
        res:array[1..maxn] of longint;
        dem,n,i,j:Longint;
        free:array[1..maxn] of boolean;
procedure nhap;
begin
    assign(input,fi);reset(Input);
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do read(b[i]);
    close(input);
end;
procedure init;
begin
    for i:=1 to n do cs[i]:=i;
end;
procedure swap(var x,y:longint);
var     w:longint;
begin
    w:=x;x:=y;y:=w;
end;
procedure qs(l,r:longint);
var     i,j,x:longint;
begin
    i:=l;j:=r;
    x:=a[(l+r) div 2];
    repeat
        while x<a[i] do inc(i);
        while x>a[j] do dec(j);
        if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    swap(cs[i],cs[j]);
                    inc(i);dec(j);
                end;
    until i>j;
    if i<r then qs(i,r);
    if j>l then qs(l,j);
end;
procedure xuly;
begin
    {f[1,0]:=b[1];}
    qs(1,n);
    for i:=2 to n do
        for j:=1 to i div 2 do
                begin
                    f[i,j]:=max(f[i-1,j],f[i-1,j-1]+b[i]);
                end;
end;
procedure trace;
begin
    i:=n; j:=n div 2;
    while (i<>0) and (j<>0) do
        begin
            if f[i,j]=f[i-1,j-1]+b[i] then
                begin
                        inc(dem);
                        res[dem]:=i;
                        free[i]:=true;
                        dec(i);dec(j);
                end else dec(i);
        end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(f[n,n div 2]);
    for i:=1 to dem do
        begin
 
            for j:=res[i]-1 downto 1 do
                if free[j]=false then
                        begin
                            write(cs[j],' ');
                            free[j]:=true;
                            break;
                        end;
            write(cs[res[i]],' ');
            writeln;
        end;
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    trace;
    inkq;
end.

SPOJ – DHLOCO

Đề bài: http://vn.spoj.com/problems/DHLOCO/

Thuật toán:

  • Sub2: QHĐ f[i] = f[i-1]+f[i-2]+f[i-3];
  • Sub3: Nhân ma trận

Code:

const
  fi='dhloco.inp';
  fo='dhloco.out';
  mt1 : array[1..3,1..3] of int64=((0,0,1) , (1,0,1) , (0,1,1));
  mt2 : array[1..3,1..3] of int64=((1,2,4) , (0,0,0) , (0,0,0));
type
  matrix = array[1..3,1..3] of int64;
var
  n : int64;
  i,j,k,m : longint;
function mul(a,b :matrix) : matrix;
  var c : matrix;
      i,j,k : longint;
  begin
    for i := 1 to 3 do
      for j := 1 to 3 do
        begin
          c[i,j] := 0 ;
          for k := 1 to 3 do
            c[i,j] := (c[i,j] + a[i,k] * b[k,j]) mod m;
        end;
    exit(c);
  end;
function power(a : matrix; y : int64) : matrix;
  var tg : matrix;
  begin
    if y = 1 then exit(a);
    tg := power(a,y shr 1);
    if y mod 2 = 0 then exit(mul(tg , tg)) else exit(mul(mul(tg,tg),a));
  end;
procedure main;
var a,b,c : matrix;
begin
 // assign(input,fi);reset(input);
 // assign(output,fo);rewrite(output);
  read(n,m);
  if n=1 then begin writeln(1 mod m); exit; end;
 
  if n=2 then begin writeln(2 mod m); exit; end;
 
  if n=3 then begin writeln(4 mod m); exit; end;
  a := mt1;
  b := mt2;
  a := power(a , n-3);
  c := mul(b,a);
  writeln(c[1,3]);
  //close(input);close(output);
end;
begin
  main;
end.

ADBRACK – SPOJ

Đề bài: http://vn.spoj.com/problems/ADBRACK/

Thuật toán

  • Bài này sử dụng phương pháp đệ quy có nhớ kết hợp với thuật toán xử lý số lớn
  • Các bạn có thể đọc code bên dưới để hiểu hơn

Code:

const   fi='';
        fo='';
        maxn=100+3;
var     f       :array[-maxn..maxn,-maxn..maxn] of ansistring;
        i,j,n,k :longint;
        st      :ansistring;
        p       :longint;
        res     :ansistring;
        stack   :array[1..maxn] of char;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n,k);
        readln(st);
        close(input);
end;
procedure init;
begin
        for i:=0 to n+1 do
                for j:=0 to n+1 do f[i,j]:='-1';
end;
function cong (a,b: ansistring): ansistring;
var     nho,tam,i:longint;
        res     :ansistring;
begin
        while length(a)<length(b) do a:='0'+a;
        while length(b)<length(a) do b:='0'+b;
        nho:=0; res:='';
        for i:=length(a) downto 1 do
                begin
                        tam:=ord(a[i])+ord(b[i])-96+nho;
                        nho:=tam div 10;
                        tam:=tam mod 10;
                        res:=chr(tam+48)+res;
                end;
        if nho>0 then res:='1'+res;
        exit(res);
end;
function tinh(i,c:longint):ansistring;
var     sl      :ansistring;
begin
        if f[i,c]<>'-1' then exit(f[i,c]);
        if i>n then
                if c=0 then
                        begin
                                f[i,c]:='1';
                                exit('1')
                        end
                        else
                        begin
                                f[i,c]:='0';
                                exit('0');
                        end;
        sl:= '0';
                if c<k then
                begin
                stack[c+1]:='(';
                sl := cong( sl, tinh(i+1,c+1) );
                stack[c+1]:='[';
                sl := cong( sl, tinh(i+1,c+1) );
                stack[c+1]:='{';
                sl := cong( sl, tinh(i+1,c+1) );
                end;
                if c>0 then
                sl := cong( sl, tinh(i+1,c-1) );
        f[i,c]:=sl;
        exit(sl);
end;
procedure timkq(i,c:longint);
begin
        if i>n then
                begin
                        res:=cong(res,'1');
                        writeln(res);
                        halt;
                end;
        if st[i]='(' then
                begin
                        stack[c+1]:='(';
                        timkq(i+1,c+1);
                end
        else
                if c<k then
                begin
                        stack[c+1]:='(';
                        res:=cong(res, tinh(i+1,c+1));
                end;
        if st[i]=')' then
                begin
                        timkq(i+1,c-1);
                end
        else
                begin
                        if c>0 then
                        if stack[c]='(' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
        if st[i]='[' then
                begin
                        stack[c+1]:='[';
                        timkq(i+1,c+1) ;
                end
        else
                if c<k then
                begin
                        stack[c+1]:='[';
                        res:=cong(res, tinh(i+1,c+1));
                end;
        if st[i]=']' then
                begin
                        timkq(i+1,c-1) ;
                end
        else
                begin
                        if c>0 then
                        if stack[c]='[' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
        if st[i]='{' then
                begin
                        stack[c+1]:='{';
                        timkq(i+1,c+1);
                end
        else
                if c<k then
                begin
                        stack[c+1]:='{';
                        res:=cong(res,tinh(i+1,c+1));
                end;
        if st[i]='}' then
                begin
                        timkq(i+1,c-1);
                end
        else
                begin
                        if c>0 then
                        if stack[c]='{' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
end;
procedure process;
var     tam:ansistring;
begin
assign(output,fo);rewrite(output);
        tam := tinh(1,0);
        res:='0';
        stack:='';
        timkq(1,0);
close(output);
end;
begin
        enter;
        init;
        process;
end.