Đoạn bao nhau 1

Cho N đoạn thẳng trên trục số với các điểm đầu a_i và điểm cuối b_i là những số nguyên trong khoảng

-1000..1000, a_i < b_i, i = 1..n. Tìm K là số lượng nhiều đoạn nhất tạo thành một dãy các đoạn bao nhau liên tiếp. Hai đoạn [a,b] và [c,d] được gọi là bao nhau nếu đoạn này nằm lọt trong đọan kia, tức là a £ c < d £  b hoặc c £ a < b £  d.

DOAN.INP	DOAN.OUT	Dữ liệu vào: tệp văn bản DOAN.INP: xem bài trước Dữ liệu ra: tệp văn bản DOAN.OUT chứa duy nhất một số tự nhiên K. Thí dụ này cho biết tối đa có 3 đoạn bao nhau là các đoạn [-1,12] Ê [8,11] Ê [8,10].
6 -1 12 8 10 8 11 2 7 17 18 13 20	3

Thuật toán

Phương pháp: Quy hoạch động.  

                Giả sử các đoạn được sắp tăng theo đầu phải b như sau. Nếu hai đoạn có cùng đầu phải thì đoạn nào có đầu trái nhỏ hơn sẽ được đặt sau.  Kí hiệu c(i) là số lượng lớn nhất các đoạn bao nhau liên tiếp trong đoạn i. Ta có,

c(1)  = 1,

Với i = 2...N:    c(i) = max { c(j) | 1 £ j < i, Đoạn j lọt trong đoạn i: a_j ³ a_i } + 1,

                Độ phức tạp: N².

                Hàm SanhDoan(x,y) thiết lập trật tự giữa hai đoạn x và y như sau:

s         Nếu x.b < y.b cho kết quả -1, nếu không: xét tiếp

s         Nếu x.b > y.b cho kết quả 1, nếu không: xét tiếp

s         Xét trường hợp x.b = y.b.

o        Nếu x.a < y.a cho kết quả 1, nếu không: xét tiếp

o        Nếu x.a > y.a cho kết quả -1, nếu không: xét tiếp

o        Hai đoạn trùng nhau: x.a = y.a và x.b = y.b cho kết qủa 0.

(*  Pascal  *)

uses crt;

const MN = 1001; bl = #32; nl = #13#10;

fn = 'doan.inp'; gn = 'doan.out';

type

Doan = record  a,b: integer;  end;

MD1 = array[0..MN] of Doan;

MI1 = array[0..MN] of integer;

var f,g: text;

d: MD1; { cac doan }

n: integer; { so doan }

procedure Doc; tự làm

function SanhDoan(x,y: Doan): integer;

begin

  if (x.b < y.b) then begin SanhDoan := -1; exit end;

  if (x.b > y.b) then begin SanhDoan := 1; exit end;

  if (x.a < y.a) then begin SanhDoan := 1; exit end;

  if (x.a > y.a) then begin SanhDoan := -1; exit end;

  SanhDoan := 0;

end;

procedure QSortB(t,p: integer);

var i,j: integer; m,x: Doan;

begin

  i := t; j := p; m := d[(i+j) div 2];

  while (i <= j) do

  begin

    while (SanhDoan(d[i],m) < 0) do i := i+1;

    while (SanhDoan(d[j],m) > 0) do j := j-1;

    if (i <= j) then

    begin

      x := d[i]; d[i] := d[j]; d[j] := x;

      i := i+1; j := j-1;

    end;

  end;

  if (t < j) then QSortB(t,j);

  if (i < p) then QSortB(i,p);

end;

function XuLi: integer;

   var c: mi1; { c[i] so doan bao nhau max }

     i,j,cmax: integer;

begin

  cmax := 0;

  for i := 1 to n do

  begin

    c[i] := 0;

    for j := i-1 downto 1 do

    begin

      if (d[j].b <= d[i].a) then break;

      if (d[j].a >= d[i].a) then

        if (c[j] > c[i]) then c[i] := c[j];

    end;

    c[i] := c[i] + 1;

    if (cmax < c[i]) then cmax := c[i];

  end;

  XuLi := cmax;

end;

procedure Ghi(k: integer);

begin

   assign(g,gn); rewrite(g); writeln(g,k); close(g);

end;

BEGIN

 Doc; QSortB(1,n); Ghi(XuLi); readln;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH