Ghép Theo Thứ Tự · canuc80k4104 · Thuật toán Canuc80k

Có $K$ khối dữ liệu nằm theo thứ tự từ trái sang phải. Khối thứ $i$ có kích thước $a_{i}$ .

Trong một thao tác, bạn chọn hai khối đang kề nhau, ghép chúng thành một khối mới có kích thước bằng tổng kích thước của hai khối. Chi phí của thao tác cũng bằng tổng đó. Thứ tự dữ liệu bên trong khối mới được giữ nguyên.

Hãy ghép toàn bộ $K$ khối thành một khối duy nhất với tổng chi phí nhỏ nhất. Bạn phải giải độc lập $T$ bộ dữ liệu.

Input

Dòng đầu chứa số nguyên $T$ - số bộ dữ liệu.
Mỗi bộ dữ liệu gồm hai dòng:
Dòng thứ nhất chứa số nguyên $K$ .
Dòng thứ hai chứa $K$ số nguyên $a_{1}, a_{2}, \dots, a_{K}$ .

Output

Với mỗi bộ dữ liệu, in trên một dòng tổng chi phí nhỏ nhất.

Constraints

$1 \leq T \leq 10$ .
$3 \leq K \leq 5000$ trong mỗi bộ dữ liệu.
$1 \leq a_{i} \leq 1 0^{4}$ .
Chỉ được ghép hai khối đang kề nhau.
Không có giới hạn bổ sung cho tổng $K$ của các bộ dữ liệu.
Kết quả phù hợp với số nguyên có dấu $64$ bit.

Scoring

Subtask $1$ ( $50%$ số điểm): Mọi bộ dữ liệu có $K \leq 25$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

15
36

Giải thích: Ở bộ thứ nhất, ghép $1$ với $4$ tốn $5$ , rồi ghép hai khối kích thước $5$ tốn $10$ , tổng là $15$ . Ở bộ thứ hai, ghép hai khối giữa tốn $4$ , sau đó ghép tiếp hai lần, lần lượt tốn $12$ và $20$ , tổng là $36$ .

Quy hoạch động khoảng: Với một bộ dữ liệu, đặt P là prefix sum và dp[l][r] là chi phí nhỏ nhất để ghép các khối từ l đến r thành một khối. Nếu phép ghép cuối cùng nối kết quả của [l,m] với [m+1,r], chi phí cuối là tổng kích thước của cả khoảng:
Quy hoạch động khoảng: dp[l][r] = P[r+1]-P[l] + min(dp[l][m] + dp[m+1][r]).
Quy hoạch động khoảng: Trạng thái một khối có chi phí bằng 0.
Knuth optimization: Trọng số khoảng là tổng các kích thước dương nên thỏa bất đẳng thức tứ giác và tính đơn điệu theo bao hàm. Vì vậy điểm chia tối ưu thỏa
Knuth optimization: opt[l][r-1] ≤ opt[l][r] ≤ opt[l+1][r].
Knuth optimization: Khi duyệt độ dài tăng dần, mỗi trạng thái chỉ quét đoạn điểm chia được chặn bởi hai trạng thái ngắn hơn. Mỗi bộ dữ liệu cần O(K²) thời gian thay vì O(K³).
Chứng minh đúng: Trong cây ghép bất kỳ, phép ghép cuối cùng chia dãy ban đầu tại đúng một vị trí m; do chỉ ghép các khối kề nhau, hai nhánh của cây lần lượt chứa hai khoảng liên tiếp [l,m] và [m+1,r]. Recurrence xét mọi vị trí như vậy và cộng đúng chi phí phép ghép cuối. Quy nạp theo độ dài khoảng chứng minh dp tối ưu. Cận Knuth luôn chứa một điểm tối ưu nên không thay đổi giá trị recurrence.
Độ phức tạp: Mỗi bộ dữ liệu dùng O(K²) thời gian và O(K²) bộ nhớ.