Gom Đá Cổ Đại

Buổi 38 — Divide & Conquer DP Dynamic Programming
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved