Nhà máy Thiên Long 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ữ...
Đọc tiếp
Nhà máy Thiên Long 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: Gồm 2 dòng
+ Dòng đầu ghi số N (1 ≤ n ≤ 100) là số công việc.
+ Dòng thứ hai ghi số N nguyên dương ai (1 ≤ ai ≤1000) là số ngày công của công
việc thứ i.
Kết quả: Một số nguyên dương là chi phí nhỏ nhất tìm được.
Ví dụ:
| Dữ liệu vào | Kết quả |
| 5 4 1 2 7 5 | 41 |
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
giúp mk với ạ!
