Ghép các đống đá
Points
52
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$.
Community Discussion