//
you're reading...
Bài tập huấn luyện, Chủ đề quy hoạch động, Lập trình Pascal nâng cao

Chuyên đề Quy hoạch động – Bố Trí Phòng Họp

[Nguồn] []


Đề bài


 Có N cuộc họp đánh số từ 1 đến N đăng ký làm việc tại một phòng hội thảo .Cuộc họp i cần đợc bắt đầu tại thời điểm Ai và kết thúc tại thời điểm Bi (i=1,2,…N). Hai cuộc họp bất kỳ chỉ đợc nhận phục vụ nếu các khoảng thời gian làm việc tơng ứng chỉ có thể đợc giao nhau tại đầu mút .Hãy tìm một lịch cho phòng hội thảo để có thể phục vụ đợc nhiều cuộc họp nhất .

Dữ Liệu:  Vào đợc cho trong file Activity.Inp gồm :

  • Dòng đầu tiên ghi giá trị N .
  • Dòng thứ i trong số N dòng tiếp ghi 2 số nguyên Ai và Bi cách nhau ít nhất một dấu trắng .

Kết Quả : Cần ghi ra file Activity.Out  nh sau :

  • Dòng đầu tiên ghi giá trị K là số cuộc họp tối đa có thể bố trí đợc
  • K dòng tiếp theo ,mõi dòng ghi số hiệu của cuộc họp đợc phục vụ theo trình tự lịch bố trí.

Giới Hạn kích thớc :

  • N không quá 10000
  • Các giá trị Ai, Bi  (i=1,2,..N) không quá 32000.

Ví Dụ:

 

Activity.Inp                                                                          Activity.Out

5   1 3   2 4   1 6   3 5   7 9                                                   3  1  4  5



Hướng dẫn


Chúng ta gọi Maxd[i] là số cuộc họp nhiều nhất có thể bố trí nếu có cuộc họp i ở trong đó.  Ta sẽ có :

Maxd[i]:=MaxMaxd[j]+1; j=0..i-1 ;

Sau đó số cuộc họp nhiều nhất có thể bố trí là giá trị lớn nhất trong số các Maxd[i] .

Chú ý :  bài toán trên có thể thay đổi cách ra đề :  coi một cuộc họp là một lần ghi âm chẳng hạn . Chính vì thế thực chất bài CDWrite và bài này là một ( nếu các bạn đã đọc bài CDWrite ,nếu cha thì các bạn chỉ cần làm bài này thôi ) .


Lời giải – Chương trình


b

b


Tài liệu tham khảo


  1. a
  2. a

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: