Quy hoạch động

QBSEQ – SPOJ

May 4, 2016 by Aida Nana Leave a Comment

Đề bài:

http://vn.spoj.com/problems/QBSEQ/

Thuật toán:

Gọi F[i][j] là độ dài dãy con dài nhất của dãy A[1..i] có tổng các phần tử chia k dư j.

Các bạn có thể tham khảo thuật toán chi tiết ở trang 162 quyển “Giải thuật và lập trình” của thầy Lê Minh Hoàng.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=1000;
  maxk=50;
var
  f : array[0..maxn,0..maxk] of longint;
  a : array[1..maxn] of longint;
  i,j,n,k : longint;
procedure enter;
  begin
    assign(input,fI);reset(input);
    readln(n,k);
    for i:=1 to n do read(a[i]);
    close(input);
  end;
function calc ( x,y : longint) : longint;
  var tg : longint;
  begin
    tg := (x-y) mod k ;
    if tg<0 then tg := tg+k;
    exit(tg);
  end;
procedure solve;
  begin
    for i:=0 to n do
      for j:=0 to k-1 do
        f[i,j] := -maxn*maxn;
    f[0,0] := 0;
    for i:=1 to n do
      for j:=0 to k-1 do
        f[i,j] := max(f[i-1,j],f[i-1,calc(j,a[i])] +1);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(f[n,0]);
    close(output);
  end;
begin
  enter;
  solve;
  print;
end.

Chủ đề: Phương pháp, Quy hoạch động, SPOJ Mức độ: day con, qbseq, QHĐ, spoj

LIQ và LIS sử dụng phương pháp quy hoạch động – SPOJ

May 2, 2016 by Aida Nana Leave a Comment

Đề bài:

Thuật toán:

Gọi L[i] là độ dài dãy con tăng dài nhất bắt đầu bằng phần tử thứ i trong dãy
L[i] = L[j] + 1 với j=i+1..n và a[j] > a[i]
Sử dụng tìm kiếm nhị phân để tính nhanh mảng L[]

Bạn hãy tham khảo cụ thể thuật toán bài này ở trang 143 quyển “Giải thuật và lập trình” – thầy Lê Minh Hoàng. Theo mình đánh giá thì đây là thuật + code chi tiết nhất, rất phù hợp cho các bạn newbie. Nếu đã hiểu rồi thì code sẽ ngắn hơn thầy nhiều 🙂

Code:

program LongestSubSequence;
const
  InputFile  = 'INCSEQ.INP';
  OutputFile = 'INCSEQ.OUT';
const
  max = 5000;
var
  a, L, T, StartOf: array[0..max + 1] of Integer;
  n, m: Integer;

procedure Enter;
var
  i: Word;
  f: Text;
begin
  Assign(f, InputFile); Reset(f);
  ReadLn(f, n);
  for i := 1 to n do Read(f, a[i]);
  Close(f);
end;

procedure Init;
begin
  a[0] := -32768;
  a[n + 1] := 32767;
  m := 1;
  L[n + 1] := 1;
  StartOf[1] := n + 1;
end;

function Find(i: Integer): Integer;
var
  inf, sup, median, j: Integer;
begin
  inf := 1; sup := m + 1;
  repeat
    median := (inf + sup) div 2;
    j := StartOf[median];
    if a[j] > a[i] then inf := median
    else sup := median;
  until inf + 1 = sup;
  Find := StartOf[inf];
end;

procedure Optimize;
var
  i, j, k: Integer;
begin
  for i := n downto 0 do
    begin
      j := Find(i);
      k := L[j] + 1;
      if k > m then
        begin
          m := k;
          StartOf[k] := i;
        end
      else
        if a[StartOf[k]] < a[i] then
          StartOf[k] := i;
      L[i] := k;
      T[i] := j;
    end;
end;

procedure Result;
var
  f: Text;
  i: Integer;
begin
  Assign(f, OutputFile); Rewrite(f);
  Writeln(f, m - 2);
  i := T[0];
  while i <> n + 1 do
    begin
      Writeln(f, 'a[', i, '] = ', a[i]);
      i := T[i];
    end;
  Close(f);
end;

begin
  Enter;
  Init;
  Optimize;
  Result;
end.

Chủ đề: Phương pháp, Quy hoạch động, Thuật toán Mức độ: day con tang, liq, lis, QHĐ

CTNOWN – SPOJ

April 29, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

(đang cập nhập)

Code:

uses    math;
const   fi='';
        fo='';
        maxn=350;
var     n,i,j   :longint;
        dem     :longint;
        nto     :array[1..maxn] of longint;
        cx      :array[1..maxn] of boolean;
        f       :array[0..maxn,0..maxn] of qword;
        t,tt,k    :longint;
        res,tam     :qword;
procedure sangnto;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxn)) do
                if cx[i]=false then
                        begin
                                j := i*i;
                                while (j<=maxn) do
                                        begin
                                                cx[j]:=true;
                                                j := j+i;
                                        end;
                        end;
        for i:=2 to maxn do
                if cx[i]=false then
                        begin
                                inc(dem);
                                nto[dem] := i;
                        end;
end;
function max(x,y : qword) : qword;
  var tg : qword;
  begin
    if x>y then exit(x) else exit(y);
  end;
procedure main;
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
        sangnto;
        read(t);
                for i:=0 to dem do
                  for j:=0 to maxn do f[i,j] := 1;
                        for i:=1 to dem do
                                begin
                                        for j:=1 to maxn do
                                        begin
                                        f[i,j] := f[i-1,j];
                                        tam:=1;
                                        while tam*nto[i]<=j do
                                                begin
                                                        tam := tam * nto[i];
                                                        f[i,j] := max(f[i,j], f[i-1,j-tam]*tam );
                                                end;
                                        end;
                                end;
        for tt := 1 to t do
                begin
                        read(n);
                        writeln(f[dem,n]);
                end;
        close(input);close(output);
end;
procedure __;
begin
end;
begin
  __ ;
  main;
  __ ;
end.

Chủ đề: Quy hoạch động, SPOJ, Thuật toán Mức độ: QHĐ

NKPALIN – SPOJ

April 3, 2016 by Aida Nana 2 Comments

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

Thuật toán:

Gọi F[i][j] là độ dài xâu đối xứng dài nhất trong đoạn S[i..j]. Khi đó:

F[i,j] = F[i+1,j-1]+2 nếu S[i] = S[j]
F[i,j] = max(F[i+1,j],F[i,j-1]) nếu S[i] <> S[j]

Bạn có thể đọc code bên dưới để hiểu hơn.

Code:

Program Xaucon;
Var s,st,st1:ansistring;
    i,j:integer;
    F: Array[1..2000,1..2000] Of Integer;

Procedure nhap;
 Begin
  Readln(s);
  For i:=1 to length(s) do F[i,i]:=1;
  Writeln;Writeln;
 end;

Function max(a,b:integer):integer;
 Begin
  If a>b then exit(a) else exit(b);
 End;


Procedure Solve;
 Begin
  For i:=length(s) downto 1 do
   For j:=i+1 to length(s) do
     If s[i]=s[j] then
         F[i,j]:=F[i+1,j-1]+2
     else F[i,j]:= max(F[i+1,j],F[i,j-1]);
   End;

Procedure PrintResult;
 Begin
  i:=1;
  j:=length(s);
    While (i<=j) do
    Begin
     If s[i]=s[j] then
       Begin
         st:=st+s[i];
         st1:=s[j]+st1;
         inc(i);
         dec(j);
       end
     Else
       If F[i+1,j]=F[i,j] then inc(i) else dec(j);
    End;
     If F[1,length(s)] mod 2 =1 then delete(st1,1,1);
    st:=st+st1;
  Writeln(st);
  end;

 Begin
 nhap;
 Solve;
 PrintResult;
readln
end.

Chủ đề: Phương pháp, Quy hoạch động, SPOJ Mức độ: NKPALIN SPOJ, QHĐ

VODIVIDE – SPOJ

February 22, 2016 by Aida Nana Leave a Comment

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

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 xa[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 il 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.

Chủ đề: Phương pháp, Quy hoạch động, SPOJ Mức độ: hsg qg, QHĐ, VODIVIDE

SPOJ – DHLOCO

February 11, 2016 by Aida Nana Leave a Comment

Đề 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.

Chủ đề: Nhân ma trận, Quy hoạch động, SPOJ Mức độ: dhloco, duyen hai, nhân ma trận, spoj

PTRANG – SPOJ

FP – SPOJ

BGBOARD – SPOJ

QBSEQ – SPOJ

LIQ và LIS sử dụng phương pháp quy hoạch động – SPOJ

CTNOWN – SPOJ

NKPALIN – SPOJ

VODIVIDE – SPOJ

SPOJ – DHLOCO

Recent Posts

Recent Comments

Archives

Categories

Meta