Gom Đá Cổ Đại
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ đống đá xếp thành một hàng ngang, đống thứ $i$ có $a_i$ viên đá. Mỗi bước, bạn được chọn hai đống đá kề nhau và gộp chúng thành một đống duy nhất; chi phí của bước gộp này bằng tổng số viên đá của hai đống đó. Hãy tìm tổng chi phí nhỏ nhất để gộ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$ ($1 \le N \le 2000$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^6$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng chi phí gộp đá nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 1 2 3 4 |
19 |
| 3 5 1 2 |
11 |
Giới hạn
- $1 \le N \le 2000$
- $1 \le a_i \le 10^6$
Community Discussion