OPTCUT - Chặt cây
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Bạn cần chặt một thanh gỗ ra thành n đoạn, mỗi đoạn có độ dài a i .
Các đoạn được chặt phải có độ dài theo đúng thứ tự a 1 , a 2 , ..., a n 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 a 1 , a 2 , ..., a n , biết rằng độ dài của thanh gỗ a 1 +a 2 +...+a n ≤ 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
- Người up: paulmcvn