Gộp Đống Sỏi Chi Phí Thấp Nhất
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ đống sỏi xếp thành một hàng ngang, đống thứ $i$ có khối lượng $a_i$. Mỗi bước, bạn được phép chọn hai đống sỏi kề nhau và gộp chúng thành một đống mới có khối lượng bằng tổng khối lượng hai đống đó; chi phí cho lần gộp này bằng khối lượng đống mới tạo thành.
Hãy lặp lại thao tác trên cho đến khi chỉ còn lại đúng một đống sỏi sao cho tổng chi phí thực hiện là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $N$ ($1 \le N \le 400$).
- Dòng thứ hai chứa $N$ số nguyên dương $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í nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 1 3 5 2 |
22 |
Giới hạn
- $1 \le N \le 400$
- $1 \le a_i \le 10^6$
Community Discussion