Bài gợi ý: CSES - Knuth Division | Phép chia Knuth
Tóm tắt: Bạn cần chia mảng \(n\) số nguyên thành \(n\) phần tử riêng lẻ qua các nhát cắt. Mỗi lần cắt một đoạn liên tiếp thành hai nửa, bạn chịu chi phí bằng tổng các số trong đoạn đó. Hãy tìm tổng chi phí nhỏ nhất để hoàn thành toàn bộ các nhát cắt.

Xét ví dụ với dãy ba số 2, 7, 3. Nhát cắt đầu tiên luôn tốn tổng chi phí của cả dãy là \(2 + 7 + 3 = 12\). Nếu bạn cắt giữa \(7\) và \(3\), mảng tách thành [2, 7] và [3], sau đó cắt tiếp [2, 7] tốn thêm \(2 + 7 = 9\), tổng chi phí là \(12 + 9 = 21\). Nếu bạn cắt giữa \(2\) và \(7\), nhát sau cắt [7, 3] tốn \(7 + 3 = 10\), tổng chi phí là \(12 + 10 = 22\). Ta thấy việc chọn vị trí cắt ở mỗi bước quyết định trực tiếp chi phí của các bước tiếp theo.

Để tìm cách cắt tốt nhất cho từng đoạn từ vị trí \(i\) đến \(j\), ta dùng quy hoạch động (phương pháp lưu lại kết quả của các đoạn ngắn để tính cho đoạn dài hơn). Gọi \(dp[i][j]\) là chi phí nhỏ nhất để chia đoạn \([i, j]\) thành từng phần tử đơn lẻ:
\(dp[i][j] = \min_{i \le k < j} (dp[i][k] + dp[k+1][j]) + \text{sum}(i, j)\)

Công thức trên nghĩa là: ta thử mọi vị trí cắt \(k\), lấy chi phí tối ưu của nửa trái \(dp[i][k]\) cộng chi phí tối ưu của nửa phải \(dp[k+1][j]\), rồi cộng thêm tổng các số \(\text{sum}(i, j)\) của cả đoạn \([i, j]\).

Với \(n = 5000\), số lượng đoạn \([i, j]\) lên tới khoảng \(1.25 \times 10^7\). Nếu mỗi đoạn ta lại duyệt biến \(k\) qua toàn bộ độ dài của nó, số phép tính sẽ lên tới cỡ \(5000^3 / 6 \approx 2 \times 10^{10}\) thao tác và làm chương trình chạy quá thời gian cho phép. Liệu ta có cần phải thử lại tất cả các vị trí \(k\) từ đầu đến cuối đoạn hay không?

Gọi \(opt[i][j]\) là vị trí cắt \(k\) tốt nhất của đoạn \([i, j]\). Vì hàm chi phí tính tổng có tính chất cộng dồn tăng dần, vị trí cắt tối ưu của đoạn \([i, j]\) luôn bị chặn bởi điểm cắt tối ưu của hai đoạn con ngắn hơn:
\(opt[i][j-1] \le opt[i][j] \le opt[i+1][j]\)

Tính chất thu hẹp này gọi là tối ưu Knuth (Knuth's optimization). Nhờ bất đẳng thức trên, thay vì duyệt toàn bộ từ \(i\) đến \(j-1\), vòng lặp \(k\) chỉ cần chạy trong đoạn hẹp từ \(opt[i][j-1]\) đến \(opt[i+1][j]\), giúp tổng số thao tác trên toàn bảng giảm xuống chỉ còn khoảng \(O(n^2)\).

Các bước cài đặt chính cho bài toán:

• Dựng mảng tiền tố pref[i] để tính nhanh \(\text{sum}(i, j) = pref[j] - pref[i-1]\).
• Khởi tạo cơ sở với đoạn độ dài \(1\): gán dp[i][i] = 0 và opt[i][i] = i cho mọi \(i\) từ \(1\) đến \(n\).
• Duyệt độ dài đoạn \(len\) tăng dần từ \(2\) đến \(n\), duyệt đầu mút trái \(i\) từ \(1\) đến \(n - len + 1\) và đặt \(j = i + len - 1\).
• Cho biến \(k\) chạy từ \(opt[i][j-1]\) đến \(\min(j-1, opt[i+1][j])\), cập nhật giá trị nhỏ nhất vào \(dp[i][j]\), lưu lại chỉ số \(k\) tối ưu vào \(opt[i][j]\), rồi in ra dp[1][n].