PVOI14_4 – spoj

November 29, 2016 by Leave a Comment

Đề 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 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 l0 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.
Chủ đề: BIT Mức độ:

QBBISHOP – spoj

October 31, 2016 by Leave a Comment

Đề bài: [xem đề bài]

covua-yeulaptrinh.pw

Thuật toán:

  • BFS từ ô (s.x,s.y)
  • Mỗi lần BFS lấy ra ô (u,v) đi theo 4 đường chéo có dạng (u-x,v-x) , (u-x,v+x) , (u+x,v-x) , (u+x,v+x).
  • Đừng quên là không thể đi đến ô đang có cờ.

Code: [xem code]

const   fi='';
        fo='';
        maxn=200;
        dx:array[1..4] of integer =(1,-1,1,-1);
        dy:array[1..4] of integer =(1,1,-1,-1);
type    point=record
                x,y:integer;
                end;
var     free:array[0..maxn+1,0..maxn+1] of boolean;
        bac:array[0..maxn+1,0..maxn+1] of integer;
        q:array[1..maxn*maxn] of point;
        n,m,i,j:integer;
        s,f:point;
        dau,cuoi,res:longint;
procedure nhap;
var     x,y:integer;
begin
    assign(input,fi);reset(input);
    readln(n,m,s.x,s.y,f.x,f.y);
    fillchar(free,sizeof(free),false);
    for i:=1 to n do
        for j:=1 to n do free[i,j]:=true;
    for i:=1 to m do
        begin
            readln(x,y);
            free[x,y]:=false;
        end;
end;
procedure init;
begin

end;
procedure push(x,y:integer);
begin
    inc(cuoi);
    q[cuoi].x:=x;
    q[cuoi].y:=y;
end;
procedure bfs;
var     u,v:point;
begin
    dau:=1;cuoi:=1;
    q[1].x:=s.x;q[1].y:=s.y;
    while dau<=cuoi do
        begin
            u:=q[dau]; inc(dau);
            for i:=1 to 4 do
                for j:=1 to n do
                        begin
                            v.x:=dx[i]*j+u.x;
                            v.y:=dy[i]*j+u.y;
                            if (v.x=f.x) and (v.y=f.y) then
                                begin
                                        res:=bac[u.x,u.y]+1;
                                        exit;
                                end;
                            if (v.x>=1) and (v.y>=1) and (v.x<=n) and (v.y<=n) and (free[v.x,v.y])  then
                                begin
                                   bac[v.x,v.y]:=bac[u.x,u.y] +1;
                                   free[v.x,v.y]:=false;
                                   push(v.x,v.y);
                                end else break;
                        end;
        end;
    res:=-1;exit;
end;
procedure xuly;
begin
    if (s.x+s.y) mod 2<>(f.x+f.y) mod 2 then begin res:=-1; exit; end;
    bfs;

end;
procedure inkq;
begin
    assign(output,fo);rewrite(Output);

    writeln(res);

    close(output);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.
Chủ đề: BFS Mức độ:

NKJUMP – spoj

October 30, 2016 by Leave a Comment

Đề bài: [xem đề bài]

Thuật toán:

  • Nhận thấy một vòng bất kỳ chỉ có thể nhảy đến vòng có số lớn hơn. Ta nghĩ đến sử dụng phương pháp Quy hoạch động để giải.
  • Ban đầu sắp xếp lại mảng A.
  • Gọi F[i] là số bước lớn nhất để nhảy đến ô thứ i.
  • F[i] = max(F[j]+1, F[i]) với i=1..n, j=1..i-1 và tồn tại k sao cho a[k]+a[j]=a[i].
  • Kiểm tra xem có tồn tại k bằng cách sử dụng tìm kiếm nhị phân

Code:

C++ (xem code trên ideone)

#include 

using namespace std;

const int maxn = 1009;
int i, j, n, a[maxn], b[maxn], f[maxn];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    int tmp, ans = 0;
    for (int i = 1; i <= n; i++) f[i] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            bool tmp = binary_search(a+1,a+j,a[i] - a[j]);
            if (tmp == 1) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

Pascal (xem code trên ideone)

uses    math;
const   fi='';
        fo='';
        maxn=1000;
type    arra=array[1..maxn] of longint;
var     f:text;
        a,l:arra;
        i,j,n:integer;
        tmp2:longint;
        res:longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do
    begin
        read(f,a[i]);
    end;
    close(f);
end;
procedure sort;
var     w:longint;
begin
    for i:=1 to n do
        for j:=i+1 to n do
        if a[i]>a[j] then
        begin
            w:=a[i];
            a[i]:=a[j];
            a[j]:=w;
        end;
end;
procedure init;
begin
    res:=0;
    for i:=1 to n do l[i]:=1;
end;
function kt(x,k:longint):boolean;
var     d,c,g,ii:longint;
begin
    d:=1; c:=k;
    kt:=false;
    while d<=c do
    begin
        g:=(d+c) div 2;
        if a[g]=x then begin tmp2:=g; exit(true); end;
        if a[g]max3 then max3:=y;
    if z>max3 then max3:=z;
end;
procedure xuly;
var     tmp:longint;
begin
    for i:=1 to n do
    begin
        tmp:=a[i];
        for j:=i-1 downto 1 do
        begin
            if a[j]>=tmp div 2 then
                begin
                   if kt(tmp-a[j],j-1) then
                        begin
                        l[i]:=max3(l[i],l[j]+1,l[tmp2]+1);
                        if l[i]>res then res:=l[i];
                        end;
                end
            else break;
        end;
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    sort;
    init;
    xuly;
    xuat;
end.
Chủ đề: Quy hoạch động, Tìm kiếm nhị phân Mức độ:

QBSELECT – spoj

October 23, 2016 by Leave a Comment

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

Tóm tắt đề bài: Cho bảng 4*n, chọn các ô không kề cạnh sao cho tổng các ô chọn lớn nhất

Ví dụ: Xét bảng với n=3 trong hình vẽ dưới đây:

QBSELECT - yeulaptrinh.pw

 

Cách chọn cần tìm là tập các ô S = {(3,1), (1,2), (4,2), (3,3)} với trọng lượng 32.

Thuật toán:

–         Theo đề bài thì bảng có 4 dòng và n cột;

  • Gọi S là trạng thái chọn các ô ở cột thứ j, ta có thể biểu diễn S bằng 4 bit (các bit được đánh số từ phải sang bắt đầu bằng 0) với ý nghĩa:

+    S[i-1] = 0: dòng thứ i của cột j không được chọn;

+    S[i-1] =1: dòng thứ i của cột j được chọn.

  • Với 4 bit, S có thể biểu diễn 16 trạng thái từ {0000} đến {1111} (từ 0 đến 15), tuy nhiên ta nhận thấy chỉ có 8 trạng thái sau là thỏa yêu cầu của bài toán: {0000}, {0001}, {0010},

{0100}, {1000}, {1001}, {0101}, {1010} (tương ứng với các giá trị 0, 1, 2, 4, 5, 8, 9, 10).

  • Gọi T[S, j] là trọng lượng lớn nhất khi chọn các ô đến cột thứ j với trạng thái chọn là S, ta có công thức quy hoạch động như sau:

T[S, j] = max(T[P, j-1] + value(S))

với P là trạng thái của cột liền trước của S sao cho P và S không có 2 bit 1 đồng thời ở cùng vị trí, còn value (S) là giá trị cách chọn cột j với trạng thái S.

  • Khi cài đặt, với bài toán này, ta chỉ cần xây dựng hàm getBit để giải mã trạng thái S
  • Còn thao tác quy hoạch động được thực hiện bình thường

Code:

uses    math;
const   fi='';
        fo='';
        maxn=10000;
        s:array[1..8] of integer = (0,1,2,4,5,8,9,10);
var     t:array[0..maxn,1..8] of longint;
        i,j,k,n:integer;
        res,tam:longint;
        a:array[1..maxn,1..4] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);

    readln(n);

    for i:=1 to 4 do
        for j:=1 to n do read(a[j,i]);

    close(input);
end;
function getbit(x,y:integer):byte;
begin
    getbit:=(x shr y) and 1;
end;
procedure xuly;
begin
    for i:=1 to n do
        for j:=1 to 8 do
        begin
            tam:=0;
            for k:=1 to 4 do tam:=tam+getbit(s[j],k-1)*a[i,k];
            for k:=1 to 8 do
              if (s[j] and s[k]=0) and (t[i-1,k]+tam>t[i,j])
                then t[i,j]:=t[i-1,k]+tam;
        end;

    res:=low(longint);
    for i:=1 to 8 do res:=max(res,t[n,i]);
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);

    tam:=low(integer);
    for i:=1 to n do
        for j:=1 to 4 do tam:=max(tam,a[i,j]);

    if tam<=0 then begin writeln(tam); halt; end;

    writeln(res);

    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
end.
Chủ đề: Quy hoạch động trạng thái Mức độ:

MPILOT – SPOJ

October 1, 2016 by 2 Comments

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

Thuật toán:

  • Đây là bài tập về thuật toán Heap cơ bản
  • Ta đưa yêu cầu bài toán thành chọn các lái phụ có chênh lệch giữa lương lái chính và lương lái phụ là lớn nhất mà vẫn đảm bảo yêu cầu có thể ghép được n/2 cặp mà tuổi lái phụ < lái chính
  • Heap sẽ lưu độ chênh lệch giữa lương lái phục và chính của mọi người
  • Duyệt i=1..n, đẩy i vào, nếu i lẻ thì lấy ở heap ra 1 thằng làm lại phụ
  • Các bạn hãy đọc code để rõ hơn

Code: [xem code]

const   fi='';
        fo='';
        maxn=10000+3;
var     p,h:array[1..maxn] of longint;
        i,j,n,res,sum:longint;
        a,c:array[1..maxn] of longint;
        nh:longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do read(a[i],c[i]);
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
function tinh(x:longint):longint;
begin
        exit(a[x]-c[x]);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j tinh(h[j]) ) then inc(j);
        if tinh(h[i]) < tinh(h[j]) then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:= i div 2;
        if i>1 then
        if tinh(h[i]) > tinh(h[j]) then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        upheap(nh);
end;
procedure process;
begin
        for i:=1 to n do
                begin
                        inc(sum,a[i]);
                        push(i);
                        if i mod 2 = 1 then inc(res,tinh(pop) );
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(sum-res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Chủ đề: Heap Mức độ: ,

VOSMAXK – spoj

October 1, 2016 by Leave a Comment

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

Thuật toán:

  • Code mình viết bên dưới rất dễ hiểu các bạn có thể tham khảo

Code:

const   inp='';
        out='';
        maxn=1000000;
var     a:array[1..maxn] of longint;
        n,k,i:longint;
        res,tmp,hold:int64;
begin
    assign(input,inp); reset(input);
    assign(output,out); rewrite(output);
    readln(n,k);
    for i:=1 to n do read(a[i]);

    res:=0; hold:=0;
    for i:=1 to n do
    begin
        if a[i]=k then
                begin
                        res:=res+(i-hold);
                        tmp:=i-hold;
                end
                else
        if a[i]>k then begin hold:=i; tmp:=0; end
        else res:=res+tmp;
    end;

    writeln(res);
    close(input); close(output);
end.
Chủ đề: SPOJ Mức độ:

PETROLM – spoj

October 1, 2016 by Leave a Comment

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

Thuật toán:

  • Đây là một bài QHĐ cơ bản suy nghĩ một chút sẽ ra
  • Các bạn hãy đọc code của mình sẽ hiểu ngay

Code:

uses math;
const
  fi='';//petrolm.inp';
  fo='';//petrolm.out';
  maxn=4000;
  oo=trunc(1e18);
type
  arr1 = array[1..maxn] of longint;
var
  tram,xe,csxe,cstram,kq : array[1..maxn] of longint;
  f : array[0..maxn,0..maxn] of int64;
  i,j,n,m : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(xe[i]);
    read(m);
    for i:=1 to m do read(tram[i]);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint; var a,b : arr1);
  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 xj;
    if il then qs(l,j,a,b);
  end;
procedure process;
  begin
    for i:=1 to n do csxe[i] := i;
    for i:=1 to m do cstram[i] := i;
    qs(1,n,xe,csxe);
    qs(1,m,tram,cstram);
    for i:=0 to n do
      for j:=0 to n do
        f[i,j] := oo;
    f[0,0] := 0;
    for i:=1 to n do f[i,i] := f[i-1,i-1] + abs(xe[i]-tram[i]);
    for j:=1 to m do
      for i:=j+1 to n do
        begin
          f[i,j] := min(f[i-1,j-1] + abs(xe[i]-tram[j]), f[i-1,j] + abs(xe[i]-tram[j]) );
          f[i,j] := f[i,j];
        end;
  end;
procedure print;
  begin
    assigN(output,fo);rewrite(output);
    writeln(f[n,m]);
    i:=n; j:= m;
    while (i>0) and (j>0) do
      begin
        if f[i,j]=f[i-1,j-1] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);dec(j);
            continue;
          end;
        if f[i,j]=f[i-1,j] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);
            continue;
          end;
      end;
    for i:=1 to n do write(kq[i],' ');
    close(output);
  end;
begin
  enter;
  process;
  print;
end.
Chủ đề: Quy hoạch động Mức độ:

BLGEN – spoj

October 1, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

Code:

uses math;
const   fi      ='';
        fo      ='';
        oo      =1000;
        maxc    =trunc(3e6);
var     n       :array[1..2] of longint;
        a       :array[1..2,1..1000] of qword;
        f       :array[0..oo,0..oo] of longint;
        mp      :longint;
        g       :array[1..maxc] of longint;
        nto     :Array[1..300000] of qword;
procedure nhap;
var     i :longint;
        k :longint;
        p :qword;
begin
        assign(input,fi);
        reset(input);
                k:=0;
                while not seekeof() do
                begin
                        inc(k);
                        while not seekeoln() do
                        begin
                                inc(n[k]);
                                read(p);
                                a[k,n[k]]:=p;
                        end;
                        readln;
                end;
        close(input);
end;
procedure sang;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxc)) do
        if g[i]=0 then
        begin
                j:=i*I;
                while j<=maxc do
                begin
                        g[j]:=i;
                        inc(j,i);
                end;
        end;
        for i:=2 to maxc do
        if g[i]=0 then
        begin
                inc(mp);
                nto[mp]:=i;
        end;
end;
function find(x:qword):boolean;
var     d,c,mid   :longint;
        t1,t2,t3      :qword;
begin
        d:=1; c:=mp;
        while d<=c do
        begin
                mid:=(d+c) div 2;
                t1:=x mod nto[mid];
                t2:=x div nto[mid];
                t3:=nto[mid]*nto[mid];
                if (t1=0) and (t2=t3) then exit(true);
                if (t3>t2) then c:=mid-1
                else d:=mid+1;
        end;
        exit(false);
end;
function kt(x:qword):boolean;
var     x1      :qword;
begin
        x1:=trunc(sqrt(x));
        if x1*x1=x then exit(true);
        if find(x) then exit(true);
        exit(false);
end;
procedure xuli;
var     i,j     :longint;
begin
        for i:=1 to n[1] do
        for j:=1 to n[2] do
        if (a[1,i]=a[2,j]) and kt(a[1,i]) then f[i,j]:=f[i-1,j-1]+1
        else f[i,j]:=max(f[i-1,j],f[i,j-1]);
end;
procedure xuat;
begin
        assign(output,fo);
        rewrite(output);
                writeln(f[n[1],n[2]]);
        close(Output);
end;
begin
        nhap;
        sang;
        xuli;
        xuat;
end.
Chủ đề: Tìm kiếm nhị phân Mức độ: ,

VDANGER – spoj

September 27, 2016 by Leave a Comment

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

Thuật toán:

  • Gợi ý là sử dụng thuật toán Floyd rồi cộng lại ra kết quả bài toán

Code:

VAR
  a :array[1..10000] of byte;
  c :array[1..100,1..100] of longint;
  t :array[1..100,1..100] of byte;
  n :byte;
  m :word;

procedure Enter;
  var i,j :word;
  begin
    readln(n,m);
    for i:=1 to m do readln(a[i]);
    for i:=1 to n do
      begin
        for j:=1 to n do
          begin
            read(c[i,j]); t[i,j]:=j;
          end;
        readln;
      end;
  end;

procedure Optimize;
  var i,j,k :byte;
  begin
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
    if (c[i,j]>c[i,k]+c[k,j]) then
      begin
        c[i,j]:=c[i,k]+c[k,j];
        t[i,j]:=t[i,k];
      end;
  end;

procedure Quit;
  var
    i :word;
    sum :longint;
  begin
    sum:=0;
    if (a[1]<>1) then sum:=sum+c[1,a[1]];
    for i:=2 to m do sum:=sum+c[a[i-1],a[i]];
    if (a[m]<>n) then sum:=sum+c[a[m],n];
    write(sum);
  end;

BEGIN
  assign(input,''); reset(input);
  assign(output,''); rewrite(output);
  Enter;
  Optimize;
  Quit;
  close(input); close(output);
END.
Chủ đề: Floyd Mức độ:

COUNTPL – spoj

September 27, 2016 by Leave a Comment

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

Thuật toán:

  • Tính trước mảng pan[i][j] = true nếu xâu s[i..j] là palindrome và ngược lại
  • Gọi f[i][j]=true nếu xâu s[1..i] có thể chia làm j xâu palindrome và ngược lại
  • Code đoạn tính f[i][j] cho các bạn dễ hiểu:
        f[0,0] := true;
        res := oo;
        for i:=1 to n do
                for j:=1 to i do
                        begin
                                for k:=i downto 1 do
                                        begin
                                                if pan[k,i] then
                                                        if f[k-1,j-1] then
                                                                f[i,j] :=true;
                                        end;
                                if i=n then if f[i,j] then res := min(res,j);
                        end;

Code:

uses    math;
const   fi='';
        fo='';
        maxn=300;
        oo=1000;
var     pan     :array[1..maxn,1..maxn] of boolean;
        i,j,n   :longint;
        s       :string;
        f       :array[0..maxn,0..maxn] of boolean;
        res     :longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(s);
        close(input);
end;
function check(i,j      :longint):boolean;
var     tg      :string;
begin
        tg := copy(s,i,j-i+1);
        for i :=1 to length(tg) div 2 do
                if tg[i]<>tg[length(tg)-i+1] then exit(false);
        exit(true);
end;
procedure process;
var     i,j,k   :longint;
begin
        n := length(s);
        for i:=1 to n do
                for j:=i to n do
                        if check(i,j) then pan[i,j] := true;
        f[0,0] := true;
        res := oo;
        for i:=1 to n do
                for j:=1 to i do
                        begin
                                for k:=i downto 1 do
                                        begin
                                                if pan[k,i] then
                                                        if f[k-1,j-1] then
                                                                f[i,j] :=true;
                                        end;
                                if i=n then if f[i,j] then res := min(res,j);
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Chủ đề: Quy hoạch động Mức độ: