Chặt cây


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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.

Bạn hãy tìm cách chặt có tổng chi phí nhỏ nhất. Lưu ý cần đảm bảo thứ tự các đoạn được chặt phải đúng thứ tự.

Dữ liệu

  • Dòng đầu tiên chứa xâu kí tự $n \ (1\le n \le 2000)$;
  • Dòng tiếp theo chứa $n$ số nguyên dương $a_i \ (1 \le a_i \le 5 \times 10^5; a_1+a_2+...+a_n \le 5\times 10^5)$.

Kết quả

  • Kết quả bài toán.

Chấm điểm

40; $n\le 10$. 60; Không có giới hạn nào thêm.

Ví dụ

Ví dụ 1

input

4
3 5 2 10

output

37

Giải thích

  • Chặt khúc gỗ độ dài 20 thành 2 khúc gỗ (10,10), chi phí 20.
  • Chặt khúc gỗ độ dài 10 đầu tiên thành 2 khúc gỗ (3,7), chi phí 10.
  • Chặt khúc gỗ độ dài 7 thành 2 khúc gỗ (5,2), chi phí 7.

Comments

There are no comments at the moment.