Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
OPTCUT - Chặt cây |
English | Vietnamese |
Bạn cần chặt một thanh gỗ ra thành n đoạn, mỗi đoạn có độ dài ai. Các đoạn được chặt phải có độ dài theo đúng thứ tự a1, a2, ..., an từ trái sang phải.
Tại mỗi bước, bạn có thể chặt một nhát chia một thanh gỗ làm hai, và chi phí cho nhát chặt này bằng độ dài của thanh gỗ trước khi chặt.
Thứ tự chặt khác nhau sẽ cho ra tổng chi phí khác nhau khi chặt thanh gỗ thành n đoạn yêu cầu.
Ví dụ bạn cần chặt một thanh gỗ độ dài 20 ra thành 4 đoạn độ dài 3, 5, 2 và 10 theo thứ tự.
Khi chặt từ trái sang phải:
20 chặt thành 3 và 17, chi phí 20.
17 chặt thành 5 và 12, chi phí 17.
12 chặt thành 2 và 10, chi phí 12.
Tổng chi phí: 49
Khi chặt từ phải sang trái:
20 chặt thành 10 và 10, chi phí 20.
10 chặt thành 8 và 2, chi phí 10.
8 chặt thành 3 và 5, chi phí 8.
Tổng chi phí: 38
Bạn hãy tìm cách chặt có tổng chi phí nhỏ nhất.
Dữ liệu
Dòng 1: n (1 ≤ n ≤ 2000)
Dòng 2: n số nguyên dương a1, a2, ..., an, biết rằng độ dài của thanh gỗ a1+a2+...+an ≤ 500000
Kết quả
Một số nguyên duy nhất là chi phí nhỏ nhất tìm được.
Ví dụ
Dữ liệu 4 3 5 2 10 Kết quả 37
Được gửi lên bởi: | Jimmy |
Ngày: | 2009-03-03 |
Thời gian chạy: | 0.200s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED |
hide comments
|
||||||
2012-05-04 13:10:42 Shinken Yellow
Tại sao lại là 37? |
||||||
2012-01-17 15:34:39 Dumbledore
20 --> 10 + 10 mất 20 10 --> 5 + 5 mất 10 5 --> 3 + 2 mất 5 tổng cộng hết 35 => ĐS là 35 chứ |
||||||
2011-09-29 10:26:57 Nguyen Dong Duc
Last edit: 2011-09-29 10:28:09 |
||||||
2011-08-23 15:10:43 Hoc nhieu vao it,Hoc it vao cung it.
Bai nay phai dung heap chu nhi. Bo tet de bai dap so phai le 35,khong phai la 37 |
||||||
2011-07-29 04:32:17 Huỳnh Quang Thảo
Sao bài này mình dùng O(N^2) mà chương trình chạy tới 2,5s lận nhỉ :( |
||||||
2011-07-06 17:01:25 Nguyen Anh
theo thứ tự j nhỉ???? nếu theo thứ tự thì kq là 38 chứ sao lại 37 |
||||||
2011-06-17 14:00:48 Le Viet Thanh Long
Bai nay qhd O(n^2) dc ah :-o |
||||||
2010-11-27 06:01:36 Lê Ðỗ Tân
Bài này QHĐ bạn ạ :D |
||||||
2009-07-02 11:49:42 chỉ là mây khói...
bài này dùng heap được không nhỉ? Last edit: 2009-07-02 11:49:58 |
||||||
2009-03-05 19:12:05 dhkhtn
Lien quan den Optimal Binary Search Tree. |