Tạo xâu đối xứng

Nguồn: CLUE OJ – Chương 22: Quy hoạch động (CHEAPPAL) Độ khó: Trung bình Quy hoạch động QHĐ đoạn

Đề bài

Cho xâu $S$ độ dài $M$ chỉ gồm các chữ cái trong tập hợp $N$ chữ cái latin in thường cho trước. Mỗi chữ cái có chi phí chèn thêm và chi phí loại bỏ.

Hãy xác định tổng chi phí ít nhất để biến $S$ thành một xâu đối xứng.

Dữ liệu:

Dòng 1: hai số nguyên $N, M$ $(1 \le N \le 26;\ 1 \le M \le 2000)$.
Dòng 2: xâu $S$ $(|S| = M)$.
Dòng $3 \ldots N + 2$: dòng $2 + i$ chứa một kí tự chữ cái $C$ và hai số nguyên $A, B$ là chi phí chèn / loại của kí tự $C$ $(0 \le A, B \le 10000)$. Không có hai dòng nào chứa cùng kí tự $C$. Các kí tự có trong $S$ đều có trong $N$ dòng này.

Kết quả: một số nguyên là tổng chi phí nhỏ nhất.

Ví dụ – input

3 4
abcb
a 1000 1100
b 350 700
c 200 800

Ví dụ – output

Giải thích ví dụ: từ abcb chèn thêm bcb vào đầu (chi phí $350 + 200 + 350 = 900$) được bcbabcb – đối xứng. Nếu xoá a (chi phí 1100) hay chèn thêm a vào cuối (chi phí 1000) đều đắt hơn.

Lời mở đầu

Bài này là bản tiếng Việt của bài Cheapest Palindrome (USACO 2007). Đây là bài QHĐ trên đoạn rất kinh điển, giống bài "thêm ít ký tự nhất để được xâu đối xứng" nhưng có thêm chi phí. Mình sẽ đi từ đệ quy thử mọi cách, sang đệ quy có nhớ, rồi QHĐ bảng – và giải thích kỹ mẹo "chèn hay xoá đều như nhau, chỉ cần lấy cái rẻ hơn".

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.

Nộp bài trên Codeforces

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test2 mức Ý tưởngmin(chèn, xoá)Cách 1Đệ quy Cách 2Có nhớ Cách 3QHĐ bảng

Bộ testBộ test chính thức có gì?

Test	Số test	$N$	$M$	Chi phí $A, B$	Đáp án
1–30	30	4	4 – 10	1 – 99	0 – 67
31–100	70	26	2.000	1 – 9.990	65.322 – 1.139.795

Đề không ghi subtask, nhưng bộ test chia rất rõ thành 2 mức: 30 test đầu xâu rất ngắn ($M \le 10$, chỉ dùng 4 chữ cái a–d; có 1 test đáp án 0 vì xâu đã đối xứng sẵn), 70 test sau đều có $M = 2000$ – lớn nhất có thể – với đủ 26 chữ cái. Đáp án lớn nhất cỡ $1{,}1 \cdot 10^6$, kiểu int là đủ (tối đa $2000 \cdot 10^4 = 2 \cdot 10^7$).

Mức	Điều kiện	Test	Cách 1 đệ quy	Cách 2 đệ quy có nhớ	Cách 3 QHĐ bảng
1	$M \le 10$	1–30	qua	qua	qua
2	$M = 2000$	31–100	quá thời gian	qua	qua

Ý tưởngXử lý 2 đầu xâu, chèn hay xoá chỉ cần chọn cái rẻ hơn

Xét đoạn $S[l..r]$. Để nó đối xứng, ký tự đầu và ký tự cuối phải "ghép cặp" được với nhau:

Nếu $S[l] = S[r]$: 2 đầu đã khớp, chỉ cần làm cho phần giữa $S[l+1..r-1]$ đối xứng.
Nếu $S[l] \ne S[r]$: ít nhất một đầu phải được xử lý. Xử lý đầu trái $S[l] = c$ có 2 cách: xoá nó (tốn $B_c$), hoặc chèn thêm một chữ $c$ vào ngay sau $S[r]$ để ghép cặp với nó (tốn $A_c$). Cả 2 cách đều đưa về cùng một bài toán con $S[l+1..r]$! Vậy chi phí xử lý ký tự $c$ chỉ cần là $$cost[c] = \min(A_c, B_c)$$ Tương tự với đầu phải $S[r]$ → bài toán con $S[l..r-1]$.

Công thức QHĐ

$f[l][r]$ = chi phí nhỏ nhất để $S[l..r]$ đối xứng; $f[l][r] = 0$ khi $l \ge r$. $$f[l][r] = \begin{cases} f[l+1][r-1] & \text{nếu } S[l] = S[r] \\ \min\big(f[l+1][r] + cost[S[l]],\ f[l][r-1] + cost[S[r]]\big) & \text{nếu } S[l] \ne S[r] \end{cases}$$ Đáp án là $f[0][M-1]$.

Ô $f[l][r]$ cần các ô ở hàng $l + 1$ (bên dưới) và ô bên trái cùng hàng, nên ta điền hàng $l$ từ dưới lên, trong mỗi hàng điền $r$ từ trái sang phải. Em sửa xâu và chi phí rồi bấm Tiếp (ô vàng đang tính, ô tím là $f[l+1][r]$ hoặc $f[l+1][r-1]$, ô cam là $f[l][r-1]$):

Xâu S Chi phí (chữ chèn xoá)

Ví dụ nhanh:

Cách 1Đệ quy thử 2 đầu – O(2ᴹ)

Viết thẳng công thức trên thành hàm đệ quy Try(l, r). Mảng cost đánh chỉ số bằng chính ký tự (kiểu char đổi ra mã ASCII) nên tra rất tiện.

C++▶ Chạy tay từng dòng codeCách 1: đệ quy Try(l, r) xử lý 2 đầu xâu.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Bên phải là ngăn xếp lời gọi; mỗi tầng ghi kết quả 2 nhánh khi đã tính xong.

Không gian$O(M)$ (độ sâu đệ quy)

Thời gian$O(2^M)$

Kết quả chạy thật: đúng 30/100 test – qua trọn mức 1 ($M \le 10$). Khi 2 đầu khác nhau, hàm gọi 2 nhánh, mỗi nhánh chỉ bớt 1 ký tự, nên số lời gọi tới cỡ $2^M$: với $M = 2000$ thì không bao giờ xong → quá thời gian cả 70 test còn lại.

Cách 2Đệ quy có nhớ – O(M²)

Hàm Try(l, r) chỉ phụ thuộc 2 tham số, nên chỉ có khoảng $\frac{M^2}{2} = 2 \cdot 10^6$ trạng thái khác nhau – thế mà cách 1 gọi tới $2^M$ lần, tức là mỗi trạng thái bị tính lặp lại vô số lần. Ta lưu kết quả vào memo[l][r]:

C++▶ Chạy tay từng dòng codeCách 2: đệ quy có nhớ, mỗi đoạn [l, r] chỉ tính 1 lần.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Ô xanh trong bảng memo nháy lên khi một lời gọi lấy lại kết quả đã lưu.

memset(memo, -1, sizeof memo) đánh dấu "chưa tính" – chi phí thật luôn $\ge 0$ nên không nhầm.
Độ sâu đệ quy tối đa khoảng $M = 2000$ tầng, an toàn.
Mảng memo $2005 \times 2005$ số int tốn 16 MB.

Không gian$O(M^2)$

Thời gian$O(M^2)$

Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,04 giây. Full điểm!

Cách 3QHĐ bảng – O(M²)

Chủ động điền bảng thay vì đệ quy: $l$ đi từ $M - 1$ về 0, $r$ đi từ $l + 1$ lên $M - 1$. Khi tính $f[l][r]$ thì hàng $l + 1$ đã xong và $f[l][r-1]$ vừa tính ngay trước.

C++▶ Chạy tay từng dòng codeCách 3: điền bảng f[l][r], l từ dưới lên, r từ trái sang.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Các ô $f[l][l] = 0$ (1 ký tự) và $f[l+1][l] = 0$ (đoạn rỗng, dùng khi $r = l + 1$ và $S[l] = S[r]$) có sẵn vì mảng toàn cục mặc định bằng 0.
Bản Python chỉ giữ 2 hàng nxt (hàng $l + 1$) và cur (hàng $l$) để đỡ tốn bộ nhớ.

Không gian$O(M^2)$ (Python: $O(M)$)

Thời gian$O(M^2)$

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,02 giây. Bản Python đúng 100/100 test – chậm nhất 0,72 giây (khoảng $2 \cdot 10^6$ phép so sánh, Python vẫn kịp nhờ chỉ dùng list và biến cục bộ).

Ghi chú của mình: Cách 1 (đệ quy) 30/100, cách 2 (đệ quy có nhớ) 100/100, cách 3 (QHĐ bảng) 100/100 với C++; Python QHĐ 2 hàng 100/100. Mẹo $cost = \min(\text{chèn}, \text{xoá})$ là chìa khoá của bài: nhờ nó mà mỗi ô chỉ còn 2 lựa chọn thay vì 4.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán