Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method HTML_content::show() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/Cache/Lite/Function.php on line 98

Strict Standards: Non-static method HTML_content::_Itemid() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 452

Strict Standards: Non-static method HTML_content::_linkInfo() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 455

Strict Standards: Non-static method HTML_content::Title() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 470

Strict Standards: Non-static method HTML_content::PdfIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 473

Strict Standards: Non-static method mosHTML::PrintIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 476

Strict Standards: Non-static method mosAdminMenus::ImageCheck() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/joomla.php on line 2329

Strict Standards: Non-static method HTML_content::EmailIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 479
Batch Scheduling - Lập kế hoạch theo khối
Strict Standards: Non-static method HTML_content::EditIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 632

Strict Standards: Non-static method HTML_content::Section_Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 511

Strict Standards: Non-static method HTML_content::Section() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 755

Strict Standards: Non-static method HTML_content::Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 758

Strict Standards: Non-static method HTML_content::Author() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 514

Strict Standards: Non-static method HTML_content::CreateDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 517

Strict Standards: Non-static method HTML_content::URL() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 520

Strict Standards: Non-static method HTML_content::ModifiedDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 536

Strict Standards: Non-static method HTML_content::ReadMore() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 539
Người viết: Ngô Minh Đức   
21/04/2008

Strict Standards: Non-static method HTML_content::TOC() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 526

Lập kế hoạch theo khối (Batch Scheduling)

Bài toán

Có một chuỗi N công việc cần một chiếc máy thực hiện. Các công việc được đánh số theo thứ tự từ 1 đến N (N). Chuỗi công việc được phân vào một hoặc nhiều khối trong đó mỗi khối chứa một số liên tục công việc liên tục theo đúng thứ tự chuỗi. Quá trình thực hiện công việc bắt đầu từ thời gian 0. Các khối được xử lý lần lượt theo nguyên tắc nếu khối b chứa các công việc với số hiệu nhỏ hơn các công việc ở khối c, thì khối b được xử lý trước khối c. Các công việc trong một khối được thực hiện liên tục. Ngay sau khi thực hiện xong tất cả các công việc trong một khối, máy sẽ đưa ra kết quả thực hiện các công việc đó. Thời gian đưa ra kết quả thực hiện công việc j là thời gian máy xử lý xong khối có chứa công việc j

Gọi S là thời gian máy chuẩn bị để xử lý mỗi khối. Với mỗi công việc i, ta có hệ số chi phí là Fi và thời gian Ti để thực hiện công việc. Nếu một khối gồm các công việc x, x+1,... , x+k và thời gian bắt đầu thực hiện công việc là t, thì tổng thời gian đưa ra kết quả cho mọi công việc trong khối là t + S + (Tx + Tx+1 +... + Ty+-k1 + Ty). Chú ý máy đưa ra kết quả cho tất cả các công việc trong khối cùng một lúc. Nếu thời gian đưa ra kết quả thực hiện công việc iOi, thì chi phí thực hiện công việc đó là Oi Fi. Ví dụ, giả sử có 5 công việc, thời gian máy chuẩn bị là S = 1, (T1, T2, T3, T4, T5) = (1, 3, 4, 2, 1) và (F1, F2, F3, F4, F5) = (3, 2, 3, 3, 4). Nếu 5 công việc trên được chia thành ba khối {1, 2}, {3}, {4, 5}, thì tổng thời gian đưa ra kết quả là (O1, O2, O3, O4, O5) = (5, 5, 10, 14, 14) và chi phí để thực hiện tất cả các công việc đó lần lượt là (15, 10, 30, 42, 56). Tổng chi phí để phân chia công việc là tổng chi phí thực hiện tất cả các công việc. Tổng chi phí của ví dụ trên là 153.

Cho trước thời gian chuẩn bị xử lý khối, chuỗi công việc, thời gian thực hiện công việc và hệ số chi phí cho trước, hãy viết chương trình tính tổng chi phí tối thiểu.

INPUT

Dòng đầu tiên chứa số công việc N, 1≤N≤10000. Dòng thứ hai chứa thời gian máy chuẩn bị để xử lý khối, thời gian S này là một số nguyên, 0≤S≤ 50. N dòng tiếp theo chứa thông tin về các công việc theo thứ tự 1, 2,..., N. Số đầu tiên trên mỗi dòng đó là số nguyên Ti, chỉ thời gian máy thực hiện công việc 1≤Ti ≤ 100. Sau đó là một số nguyên Fi, 1 ≤Fi ≤ 100, chỉ hệ số chi phí thực hiện công việc.

OUTPUT

Output là một dòng chứa một số nguyên chỉ tổng chi phí tối thiểu.

Ví dụ

INPUT và OUTPUT

Ví dụ 2 là ví dụ xét đến ở trên.

Chú ý

Với mọi bộ dữ liệu test, tổng chi phí đều không vượt quá 231 - 1.

Cho điểm

Nếu chương trình đưa ra kết quả đúng trong khoảng thời gian giới hạn, bạn sẽ được điểm tối đa, ngược lại bạn sẽ được 0 điểm.
 
Strict Standards: Non-static method HTML_content::Navigation() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 550

Strict Standards: Non-static method mosHTML::CloseButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 553

Strict Standards: Non-static method mosHTML::BackButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 556