Ghép các đống đá

Buổi 65-66 — Mock HSG Dynamic Programming dynamic-programming
Points
52
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ đống đá xếp thành một hàng ngang, đống thứ $i$ có $A_i$ viên đá. Trong mỗi bước, bạn chọn hai đống đá kề nhau và ghép chúng lại thành một đống mới có số đá bằng tổng số đá của hai đống đó; chi phí của bước ghép này cũng chính là tổng số đá của hai đống được ghép. Hãy tìm tổng chi phí nhỏ nhất để ghép tất cả $N$ đống đá thành một đống duy nhất.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.
Dữ liệu ra

In ra tổng chi phí nhỏ nhất.

Ví dụ
Input Output
4
1 2 3 4
19
1
100
0
Giới hạn

$1 \le N \le 300$, $1 \le A_i \le 10^6$.

Draft saved