Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Diễn đàn arrow Thư viện arrow Đề thi arrow VOI (thi quốc gia) arrow 2003 arrow Batch Scheduling - Lập kế hoạch theo khối
Batch Scheduling - Lập kế hoạch theo khối In E-mail
(1 vote)
Người viết: Ngô Minh Đức   
21/04/2008

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.
 
< Trước   Tiếp >