Các Toa Yên Tĩnh · canuc80k4102 · Thuật toán Canuc80k

Có $N$ hành khách đứng theo thứ tự từ $1$ đến $N$ . Bạn phải chia họ vào đúng $K$ toa, sao cho mỗi toa nhận một đoạn liên tiếp không rỗng của thứ tự ban đầu.

Ma trận $u$ mô tả mức xung đột giữa từng cặp hành khách. Ma trận đối xứng, $u_{i} [i] = 0$ . Nếu một toa chứa các hành khách từ $l$ đến $r$ , chi phí của toa là tổng $u_{i} [j]$ trên mọi cặp $l \leq i < j \leq r$ . Tổng chi phí là tổng chi phí của $K$ toa.

Hãy tìm tổng chi phí nhỏ nhất.

Input

Dòng đầu chứa hai số nguyên $N$ và $K$ .
$N$ dòng tiếp theo, mỗi dòng là một chuỗi đúng $N$ chữ số. Chữ số thứ $j$ của dòng $i$ là $u_{i} [j]$ .

Output

In ra một số nguyên: tổng chi phí nhỏ nhất.

Constraints

$1 \leq N \leq 4000$ .
$1 \leq K \leq min (N, 800)$ .
Mỗi ký tự ma trận là một chữ số từ $0$ đến $9$ .
$u_{i} [i] = 0$ và $u_{i} [j] = u_{j} [i]$ với mọi i, j.
Mỗi toa phải chứa ít nhất một hành khách.
Kết quả phù hợp với số nguyên có dấu $64$ bit.

Scoring

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

Example

Test 1

Input

Output

Giải thích: Chia thành hai toa $[1, 2]$ và $[3, 5]$ . Chi phí lần lượt là $2$ và $2 + 7 + 1 = 10$ , nên tổng bằng $12$ . Chia thành $[1, 3]$ và $[4, 5]$ cũng đạt $12$ ; các ranh giới còn lại đều có chi phí lớn hơn.

Tiền xử lý chi phí: Gọi W(l,r) là tổng xung đột của mọi cặp trong đoạn [l,r]. Ta lưu prefix sum cho từng hàng ma trận. Khi mở rộng [l,r-1] thành [l,r], các cặp mới chính xác là (i,r) với l≤i<r; tổng của chúng lấy trong O(1) từ prefix hàng r. Nhờ đó toàn bộ bảng W được tính trong O(N²).
Quy hoạch động và tối ưu: Đặt dp[g][r] là chi phí nhỏ nhất khi chia r hành khách đầu thành đúng g toa. Với điểm chia cuối p:
Quy hoạch động và tối ưu: dp[g][r] = min(dp[g-1][p] + W(p+1,r)).
Quy hoạch động và tối ưu: Do mọi phần tử ma trận không âm, W thỏa bất đẳng thức Monge: phần chênh lệch của hai vế bằng âm tổng trọng số giữa hai khối ngoài. Vị trí tối ưu trên mỗi hàng DP vì thế không giảm, cho phép tính hàng bằng Divide and Conquer.
Chứng minh đúng: Công thức tiền xử lý thêm đúng các cặp có đầu mút mới r, không bỏ sót và không đếm trùng. Mọi cách chia có duy nhất điểm chia cuối, nên recurrence xét đủ. Tính Monge bảo đảm khoảng tối ưu của thủ tục chia để trị luôn chứa nghiệm tốt nhất. Suy ra dp[K][N] là tổng nhỏ nhất.
Độ phức tạp: Tiền xử lý O(N²), DP O(KN log N), bộ nhớ O(N²).