//
you're reading...
Bài tập huấn luyện, Đề thi cấp tỉnh - Đồng Tháp

Bài tập huấn luyện: DÂY CHUYỀN SẢN XUẤT


Đề bài – HSG 12 THPT vòng tỉnh (Năm 2011)


Nhà máy Bích Chi cần kết hợp N công việc thành một dây chuyền sản xuất. Công việc thứ i cần ai ngày công. Mỗi công đoạn sản phẩm là kết hợp 2 công việc liên tiếp lại với nhau thành một công việc với chi phí cho công đoạn này bằng tổng ngày công của 2 công việc đó.

Yêu cầu: Bạn hãy giúp nhà máy ghép N công việc đó thành dây chuyền bằng N-1 công đoạn sản phẩm sao cho tổng chi phí các công đoạn là nhỏ nhất.

Dữ liệu vào: từ tệp văn bản SXUAT.INP có dạng:

  • Dòng đầu ghi số N (1<=N<=100) là số công việc.
  • Dòng thứ i trong N dòng tiếp theo ghi số nguyên dương ai là số  ngày công của công việc thứ i    (ai < 1000).

Kết quả: ghi ra tệp văn bản SXUAT.OUT có một số nguyên dương là chi phí nhỏ nhất tìm được.

Ví dụ:

SXUAT.INP SXUAT.OUT
5 41
4
1
2
7
5

– Giải thích:

4 2 1 7 5
4   3 7 5
7 7 5
7   12
19

Tổng chi phí: 3+7+12+19=41

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

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: