Ý tưởng:

• Hồ Ngọc Vĩnh Phát - VNUHCM-University of Science

Biên soạn:

• Đặng Minh Nhựt - THPT chuyên Long An - Long An

Nhận xét 1

Sau khi thực hiện các thao tác chuyển vị trí của các quả táo (lấy ra tại vị trí ~i~ và chèn vào vị trí ~j~ mới), sẽ tồn tại hai loại quả táo: được chuyển đi vị trí khác (không cố định) và không được chuyển (cố định).

Ta sẽ quan sát thấy các quả táo cố định sẽ là những quá táo mà theo thứ tự ban đầu có thể đặt lần lượt vào ~k~ đoạn sao cho thỏa mãn điều kiện của từng đoạn. Vì vậy ta cũng không cần quan tâm về các quả táo không cố định vì chúng sẽ được chuyển về vị trí đúng sau đó (ta có thể xem thao tác chuyển như thao tác bỏ các quả táo đó ra khỏi dãy).

Như vậy để tìm đáp án, ta đi tìm số lượng phần tử nhỏ nhất cần bỏ ra khỏi dãy để có thể chia các phần tử còn lại theo thứ tự vào ~k~ đoạn sao cho đúng vị trí đề bài yêu cầu.

Thuật ~O(n^3/k)~

Gọi ~dp[i][part]~ là số phần tử nhỏ nhất phải bỏ ra khi xét dãy từ ~1~ đến ~i~ và đến đoạn thứ ~part (1 \leq part \leq n/k)~. Ta có công thức quy hoạch động như sau:

~dp[i][part] = \min_{1 \leq j \leq i} dp[j][part-1] + k - C~

Với ~k~ là số phần tử mỗi đoạn đề cho, ~C~ là số phần tử tối đa trong đoạn con ~[j+1, i]~ có thể dùng để điền vào đoạn thứ ~part~.

Ta có thể tính mảng này một cách "ngây thơ" trong ~O(n^3/k)~ với chi phí chuyển là ~O(n)~.

Nhận xét 2

Để giảm độ phức tạp thuật toán, ta tìm cách giảm độ phức tạp của chi phí chuyển.

Ta nhận thấy với cách "ngây thơ" ở trên, ta phải duyệt qua tất cả các vị trí ~j \leq i~ để tìm ~C~. Tuy nhiên với mỗi giá trị ~C~ ta chỉ cần quan tâm vị trí ~j~ nằm phải nhất (lớn nhất) bởi vì ~j~ càng lớn thì ta càng có thể chọn nhiều phần tử cố định hơn trong đoạn con ~[1, j]~ (nói cách khác: ~dp[i][part] \geq dp[i+1][part]~ ~\forall 1 \leq i < n~).

Thuật ~O(n^2)~

Ta gọi ~prev[i][part][cnt]~ là vị trí ~j \leq i~ lớn nhất sao cho trong đoạn con ~[j+1, i]~ của dãy ban đầu ta có thể điền ít nhất ~cnt~ phần tử vào đoạn thứ ~part~. Để tính mảng này, ta có thể cố định ~part~ và ~cnt~ rồi dùng kĩ thuật hai con trỏ để tính trong ~O(n \cdot \frac{n}{k} \cdot k) = O(n^2)~

Nhờ vậy, bây giờ ta có thể chuyển trạng thái hàm quy hoạch động trong ~O(k)~ như sau:

~dp[i][part] = \min_{0 \leq cnt \leq k} dp[prev[i][part][cnt]][part-1] + k - cnt~

Độ phức tạp thuật toán sẽ là ~O(n \cdot \frac{n}{k} \cdot k) = O(n^2)~.