Nhận xét 1: Trong một đáp án tối ưu, nếu ta thực hiện thao tác trên ~m~ đoạn ~[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]~, ta có: ~[l_i, r_i] \cap [l_j, r_j] = \varnothing\ \forall i < j~.

Nhận xét 2: Gọi ~cnt_s[i, c]~ là số lượng kí tự ~c~ nằm trong đoạn ~s[1..i]~. Để thực hiện thao tác trên đoạn ~[l, r]~, ta phải có ~cnt_s[r, c] - cnt_s[l - 1, c] = cnt_t[r, c] - cnt_t[l - 1, c]~ với mọi kí tự tiếng Anh ~c~.

Từ đây, ta có ý tưởng cho bài toán như sau:

Subtask 2

Gọi ~f[i][j]~ là thời gian nhỏ nhất để đưa xâu ~s[1..i]~ về xâu ~t[1..i]~ sau tối đa ~j~ lượt.

Để thuận tiện cho việc biểu diễn thuật toán, ta đặt thêm một mảng ~good[i]~: có thể đưa xâu ~s[1..i]~ về xâu ~t[1..i]~ không? Việc tính toán mảng ~good[i]~ có thể thực hiện bằng cách sử dụng mảng ~cnt_s~ và ~cnt_t~ ở nhận xét 2.

Ta sẽ xem xét các trạng thái chuyển quy hoạch động như sau:

• ~f[0][j] = 0~
• nếu ~j > 0~: ~f[i][j] = f[i][j - 1]~
• nếu ~s[i] = t[i]~: ~f[i][j] = f[i - 1][j]~
• nếu ~j > 0~ và ~good[i] = 1~: ~f[i][j] = \min \limits_{p < i,\ good[p] = 1} f[p][j - 1] + (a[p + 1] + a[p + 2] + \ldots + a[i])~.

Đáp án của bài toán là ~f[n][k]~, và độ phức tạp của thuật toán này là ~O(nk)~.

Subtask 3

Ta sẽ sử dụng hai con trỏ để tìm toàn bộ các đoạn ~[l, r]~ thỏa mãn điều kiện trong nhận xét 2. Giả sử ta tìm được ~m~ đoạn thỏa mãn điều kiện:

• nếu ~m \le k~, đây là một đáp án tối ưu.
• ngược lại, ta cần phải giảm số lượng đoạn bằng cách hợp hai đoạn liên tiếp ~[l_i, r_i]~ và ~[l_{i + 1}, r_{i + 1}]~ thành một đoạn duy nhất ~[l_i, r_{i + 1}]~ với chi phí thêm là ~a[r_i + 1] + a[r_i + 2] + \ldots + a[l_{i + 1} - 1]~, và ta cần phải hợp ~m - k~ lần. Để tìm được cách hợp tối ưu, ta có thể tham lam bằng cách hợp từ chi phí nhỏ nhất.