Atcoder Educational DP Contest N - Slimes

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ cục thạch xếp thành một hàng ngang. Ban đầu, cục thạch thứ ~i~, đếm từ trái sang, có kích thước ~a_i~.

Taro cố gắng ghép những cục thạch này lại với nhau để tạo thành một cục thạch lớn hơn. Anh ấy sẽ liên tục lặp lại thao tác sau cho đến khi chỉ còn lại một cục thạch duy nhất:

  • Taro chọn hai cục thạch kế bên nhau và ghép chúng lại. Cục thạch mới sẽ có kích thước là ~x+y~, ~x~ và ~y~ là kích thước của hai cục thạch được chọn trước khi được ghép. Chi phí phát sinh là ~x+y~ và vị trí tương đối giữa các cục thạch là không thay đổi trong suốt quá trình kết hợp các cục thạch.

Taro là một người tiết kiệm. Bạn hãy giúp Taro tìm chi phí phát sinh nhỏ nhất có thể.

Input

Dòng đầu tiên chứa số nguyên ~N(2 \leq N \leq 400)~ là số lượng cục thạch.

Dòng thứ hai chứ ~N~ số nguyên ~a_1,a_2,a_3,...,a_n (1 \leq a_i \leq 10^9)~.

Output

Dòng duy nhất là chi phí phát sinh nhỏ nhất.

Sample 1

Input
4
10 20 30 40
Output
190

Taro nên thực hiện như sau (những cục thạch được ghép sẽ được in đậm).

  • (10, 20, 30, 40) → (30, 30, 40)
  • (30, 30, 40) → (60, 40)
  • (60, 40) → (100)

Sample 2

Input
5
10 10 10 10 10
Output
120

Taro có thể thực hiện các thao tác như dưới đây:

  • (10, 10, 10, 10, 10) → (20, 10, 10, 10)
  • (20, 10, 10, 10) → (20, 20, 10)
  • (20, 20, 10) → (20, 30)
  • (20, 30) → (50)

Sample 3

Input
3
1000000000 1000000000 1000000000
Output
5000000000

Câu trả lời có thể không vừa kiểu int.

Sample 4

Input
6
7 6 8 6 1 1
Output
68

Taro nên thực hiện các thao tác như sau:

  • (7, 6, 8, 6,1, 1) → (7, 6, 8, 6, 2)
  • (7, 6, 8, 6, 2) → (7, 6, 8, 8)
  • (7, 6, 8, 8) → (13, 8, 8)
  • (13, 8, 8) → (13, 16)
  • (13, 16) → (29)

Comments

Please read the guidelines before commenting.


There are no comments at the moment.