OPTCUT - Chặt cây

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/optcut


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

Added by:Jimmy
Date:2009-03-03
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO PERL6

hide comments
2021-05-20 20:56:14 Simes
The order of the final sizes of the pieces of wood cannot vary, but the order of the cuts that produces those pieces can vary.
20 -> 3 + 17 -> 3 + 5 + 12 -> 3 + 5 + 2 + 10, for a cost of 20 + 17 + 12 = 49
20 -> 10 + 10 -> 8 + 2 + 10 -> 3 + 5 + 2 + 10, for a cost of 20 + 10 + 8 = 38
20 -> 10 + 10 -> 3 + 7 + 10 -> 3 + 5 + 2 + 10, for a cost of 20 + 10 + 7 = 37


Last edit: 2021-07-03 22:54:08
2021-05-20 11:39:47
I don't understand. The vietnamese statement translates:

Different cutting orders will result in different total costs when cutting the log into the required n segments.
(example of two different cutting orders)
Find the way to chop with the lowest total cost.

What can the cost depend on if the order does not vary?
2021-05-19 17:06:41 [Rampage] Blue.Mary
@nadstratosfer: The order can't be changed. So 10 -> 5 + (5) is invalid.
2021-05-19 15:30:27
(20) -> 10 + (10) -> 5 + (5) -> 3+2, total cost = 35. Why does the sample show 37?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.