Bài gợi ý: CSES - Knuth Division | Phép chia Knuth
Tóm tắt: Bạn có một dãy gồm \(N\) số nguyên. Ở mỗi bước, bạn chọn một đoạn liên tiếp và tách thành hai đoạn con nhỏ hơn, chi phí bằng tổng các số trong đoạn đó. Nhiệm vụ là tìm tổng chi phí nhỏ nhất để tách toàn bộ mảng thành từng phần tử đơn lẻ.

Thay vì nghĩ theo chiều tách mảng lớn, ta có thể lật ngược bài toán thành thao tác gộp các đoạn kề nhau. Chẳng hạn với mảng ba số \([2, 7, 3]\), nếu bạn gộp \(7\) và \(3\) trước thì tốn chi phí \(7 + 3 = 10\). Sau đó bạn gộp số \(2\) với đoạn \([7, 3]\) vừa tạo, chi phí tốn thêm \(2 + 10 = 12\). Tổng chi phí của cách làm này là \(10 + 12 = 22\).

Để tìm chi phí nhỏ nhất, ta dùng quy hoạch động (DP - phương pháp giải bài toán lớn thông qua kết quả của các bài toán con nhỏ hơn). Gọi \(dp[i][j]\) là chi phí nhỏ nhất để gộp các phần tử từ vị trí \(i\) đến \(j\). Ta thử mọi vị trí cắt \(k\) nằm giữa \(i\) và \(j-1\) để chia đoạn thành \([i, k]\) và \([k+1, j]\). Công thức chuyển trạng thái là \(dp[i][j] = \min_{i \le k < j} (dp[i][k] + dp[k+1][j]) + \text{sum}(i, j)\), trong đó \(\text{sum}(i, j)\) là tổng các phần tử từ \(i\) đến \(j\).

Với giới hạn \(N \le 5000\), nếu duyệt mọi cặp \((i, j)\) rồi duyệt tiếp \(k\) từ \(i\) đến \(j\), số phép tính sẽ lên tới khoảng \(5000^3 / 6 \approx 2 \times 10^{10}\) thao tác. Cách làm này chắc chắn sẽ chạy quá thời gian cho phép. Ta cần một cơ chế để thu hẹp phạm vi duyệt của điểm cắt \(k\).

Gọi \(opt[i][j]\) là vị trí \(k\) tối ưu giúp \(dp[i][j]\) đạt giá trị nhỏ nhất. Điểm mấu chốt của bài toán là tính đơn điệu của điểm cắt: vị trí tối ưu \(opt[i][j]\) luôn bị kẹp giữa \(opt[i][j-1]\) và \(opt[i+1][j]\). Kỹ thuật này được gọi là tối ưu hóa Knuth. Nhờ đó, ta chỉ cần duyệt \(k\) trong đoạn \([opt[i][j-1], opt[i+1][j]]\), giúp giảm tổng độ phức tạp toàn bài xuống chỉ còn khoảng \(N^2 / 2 \approx 1.25 \times 10^7\) phép tính.

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

• Dùng mảng tiền tố để tính nhanh \(\text{sum}(i, j) = \text{pref}[j] - \text{pref}[i-1]\).
• Khởi tạo cơ sở \(dp[i][i] = 0\) và \(opt[i][i] = i\) với mọi \(i\) từ \(1\) đến \(N\).
• Lặp độ dài đoạn \(\text{len}\) từ \(2\) đến \(N\), chọn đầu mút trái \(i\) và xác định đầu mút phải \(j = i + \text{len} - 1\).
• Cho \(k\) chạy trong khoảng từ \(opt[i][j-1]\) đến \(opt[i+1][j]\) để tìm giá trị nhỏ nhất cho \(dp[i][j]\), đồng thời lưu lại vị trí tối ưu vào \(opt[i][j]\).

Bài tập tương tự:

• SEQPART (IOI'14): Luyện tập kỹ thuật tối ưu hóa quy hoạch động trên các đoạn số và tối ưu chia để trị [cite: 1].

Bạn hãy khai báo mảng long long dp[5005][5005], mảng int opt[5005][5005], khởi tạo mảng cộng dồn tiền tố và in ra kết quả tại dp[1][n].