Đoạn gối 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. Hãy tìm số lượng tối đa K đoạn thẳng gối nhau liên tiếp. Hai đoạn thẳng [a,b] và [c,d] được gọi là gối nhau nếu xếp chúng trên cùng một trục số thì điểm đầu đoạn này trùng với điểm cuối của đoạn kia, tức là c = b hoặc d = a.

DOAN.INP	DOAN.OUT	Dữ liệu vào: tệp văn bản DOAN.INP: xem Đoạn gối 1 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 có tối đa 3  đoạn gối nhau liên tiếp là [1,3], [3,4] và [4,5].
5 2 7 1 3 7 9 3 4 4 5	3

Thuật toán

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

Giả sử các đoạn được sắp tăng theo đầu phải b. Kí hiệu c(i) là số lượng tối đa các đoạn thẳng gối nhau tạo thành một dãy nhận đoạn i làm phần tử cuối dãy (khi khảo sát các đoạn từ 1..i). Ta có

c(1) =1,

Với i = 2...N:  c(i) = max { c(j) | 1 £ j < i, Đoạn j kề trước đoạn i:  b_j = a_i } + 1.

Lợi dụng các đoạn sắp tăng theo đầu phải b, với mỗi đoạn i  ta chỉ cần duyệt ngược các đoạn j đứng trước đoạn i cho đến khi phát hiện bất đẳng thức b_j < a_i.  

Kết quả: K = max { c(i)  | i = 1...n }.

Độ phức tạp: cỡ N² vì với mỗi đoạn  ta phải duyệt tối đa tất cả các đoạn đứng trước đoạn đó.

(* Pascal *)

 (*============================

    Đoạn Gối 1: Số lượng tối đa

    các đoạn gối nhau.

  ============================*)

program DoanGoi1;

uses crt;

const

  mn = 1001; bl = #32; nl = #13#10;

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

type

  KieuDoan = record a,b: integer; end;

  md1 = array[0..mn] of KieuDoan;

  mi1 = array[0..mn] of integer;

var n,m: integer; { n – số lượng đoạn, m – số đoạn được chọn }

    d: md1; { các đoạn d[1..n]}

    f,g: text;

    c: mi1; { c[i] = số lượng max các đoạn gối nhau đến i }

procedure Doc; tự viết

procedure Qsort(t,p: integer);tự viết

procedure XuLi;

var i,j: integer;

begin

  c[1] := 1;

  for i := 2 to n do { Tính c[i] }

    begin

      c[i] := 0;

        for j := i-1 downto 1 do

          begin

            if (d[j].b < d[i].a)  { doan j khong noi voi i }

            then break;

            if (d[j].b = d[i].a) then { j noi voi i }

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

          end;

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

    end;

end;

procedure Ket; { Tim c max va hien thi ket qua }

var i,imax: integer;

begin

  assign(g,gn); rewrite(g);

  imax := 1;

  for i := 2 to n do

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

  writeln(g,c[imax]); close(g);

end;

BEGIN

  Doc; Qsort(1,n); XuLi;  Ket;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH