Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

OPTCUT - Chặt cây

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:Duc
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
2018-01-09 15:24:11
Làm sao O(N^2) nhỉ. Chẳng lẽ mỗi lần đều chặt rìa.
2017-08-29 03:31:06
O(n) và dell qua test 1. đm
2017-03-01 09:30:51
ai biết test 1 là j ko v @@
2016-11-21 16:48:50
test kiểu gì mà WA ở test 1 thế nhỉ
2016-07-09 21:11:11 noname00.pas
Mình có tham khảo bài viết về "Quy học động tăng tốc"
Code
http://ideone.com/DE4kj0
2015-09-08 14:10:34
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-05-07 04:09:12 lucky++
A di đà phật. Nhị phân sai, O(N3) quá lâu, O(N2) AC, mất toi cả ngày.
2014-08-21 20:30:53 Thcs Ðặng Chánh Kỷ
đề có vẻ khó hiểu nhưng thực chất là ghép 2 số kề nhau sao cho chi phí min, thế thôi đáp án 37 là cả 1 quá trình mày mò để hiểu được cái đề siêu ảo lòi này, để làm đc nó mất cả 1 buổi tối với độ phức tạp>n^2<n^3, nói chung là sướng
2014-08-01 19:08:35 Prismatic


Last edit: 2014-08-01 19:14:24
2014-08-01 19:08:34 Prismatic


Last edit: 2014-08-01 19:14:34
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.