Gộp Các Khối Kề Nhau · canuc80k1228

Có $N$ khối vật liệu nằm thành một hàng, khối thứ $i$ có kích thước $A_{i}$ . Trong một thao tác, chỉ được chọn hai khối đang kề nhau, có kích thước $x$ và $y$ , rồi thay chúng bằng một khối mới kích thước $x + y$ ; thứ tự của các khối còn lại không đổi. Thao tác này tốn chi phí $x + y$ . Hãy tìm tổng chi phí nhỏ nhất để cuối cùng chỉ còn một khối.

Input

Dòng đầu chứa số nguyên $N$ .
Dòng thứ hai chứa $N$ số nguyên $A_{1}, A_{2}, \dots, A_{N}$ .

Output

In một số nguyên: tổng chi phí nhỏ nhất để gộp toàn bộ dãy thành một khối.

Constraints

$2 \leq N \leq 400$ .
$1 \leq A_{i} \leq 1 0^{9}$ với mọi $i$ .
Sau mỗi lần gộp, khối mới chiếm đúng vị trí của cặp đã chọn; do đó chỉ các đoạn liên tiếp ban đầu có thể tạo thành một khối trung gian.

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 9$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

4
2 2 1 2

Output

Giải thích: Gộp hai khối đầu thành $4$ với chi phí $4$ , gộp hai khối cuối thành $3$ với chi phí $3$ , rồi gộp $4$ và $3$ với chi phí $7$ . Tổng là $4 + 3 + 7 = 14$ ; không có lịch gộp nào có tổng chi phí nhỏ hơn $14$ .

Ý tưởng: Đặt dp[l][r] là chi phí nhỏ nhất để gộp đoạn khối ban đầu từ l đến r thành một khối. Trong thao tác cuối của đoạn, khối trái phải đến từ [l,k] và khối phải từ [k+1,r] với một k nào đó. Vì kích thước khối cuối bằng tổng cả đoạn, chuyển là dp[l][k]+dp[k+1][r]+sum(l,r). Prefix sum cho phép lấy sum(l,r) trong O(1).
Chứng minh tính đúng đắn: Do chỉ gộp các khối kề và thứ tự không đổi, ngay trước thao tác cuối trên đoạn [l,r], hai khối phải tương ứng với một tiền tố [l,k] và hậu tố [k+1,r]. Mỗi nửa phải được gộp tối ưu, nếu không có thể thay bằng cách rẻ hơn. Chi phí thao tác cuối luôn bằng tổng kích thước toàn đoạn. Thuật toán thử mọi điểm chia k, nên xét đầy đủ mọi cây gộp hợp lệ; lấy nhỏ nhất cho giá trị tối ưu. Quy nạp theo độ dài đoạn hoàn tất chứng minh.
Độ phức tạp: Thời gian O(N^3) và bộ nhớ O(N^2).