Đoạn gối 3

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. Liệt kê các đoạn thẳng gối nhau có tổng chiều dài C lớn nhất.

DOAN.INP	DOAN.OUT	Dữ liệu vào: tệp văn bản DOAN.INP: xem bài Đoạn gối 1. Dữ liệu ra: tệp văn bản DOAN.OUT Dòng đầu tiên: số tự nhiên C. Mỗi dòng tiếp theo chứa một số tự nhiên biểu thị chỉ số của đoạn thẳng gối nhau liên tiếp trong dãy tìm được. Thí dụ này cho biết hai đoạn 2  và 4 tạo thành dãy đoạn gối nhau liên tiếp có tổng chiều dài max là 39.
8 2 7 1 3 7 9 3 40 3 5 2 3 5 9 9 16	39 2 4

Thuật toán

Phương pháp: Quy hoạch động kết hợp với con trỏ trước t để giải trình kết quả.  

Giả sử các đoạn được sắp tăng theo đầu phải b. Kí hiệu c(i) là tổng chiều dài lớn nhất các đoạn thẳng gối nhau liên tiếp 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). Để ý rằng (b_i -  a_i) là chiều dài đoạn thứ i, ta có

c(1)  = chiều dài đoạn 1 = b₁ - a₁,

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 } + (b_i -  a_i), 

Nếu j là chỉ số đạt max thì đặt t_i =  j.

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

(*  Pascal  *)

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

    Doan Goi 3: Liet ke cac doan goi nhau

                co tong chieu dai max

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

program DoanGoi3;

uses crt;

const

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

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

type

  KieuDoan = record a,b,id: 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;

    f,g: text;

    c: mi1; {c[i] = chieu dai max nhan i lam doan cuoi}

    t: mi1; { tro truoc }

procedure Doc; tự viết

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

procedure XuLi;

var i,j,jmax: integer;

begin

  fillchar(t,sizeof(t),0);{ Khơỉ tạo mảng trỏ trước }

  c[1] := d[1].b - d[1].a; { Chieu dai doan 1 }

  for i := 2 to n do

    begin

      c[i] := 0; jmax := i;

        for j := i-1 downto 1 do

          begin

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

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

               if (c[j] > c[jmax]) then

                         jmax := j;                

          end;

      c[i] := c[jmax] + (d[i].b - d[i].a); t[i] := jmax;

    end;

end;

procedure GiaiTrinh(i: integer); tự viết

procedure Ket; tự viết

BEGIN

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

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH