Hướng dẫn giải của Xâu đối xứng
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Số ký tự ít nhất cần thêm để xâu ~S~ thành xâu đối xứng (nếu đã đối xứng thì là 0). Gọi ~f[l][r]~ là số ký tự tối thiểu cần thêm để đoạn ~S[l..r]~ đối xứng.
Sub 1: Đệ quy vét cạn — ~O(2^n)~, dùng khi ~n \le 20~
Xét hai đầu đoạn: nếu ~S[l] = S[r]~ thì bỏ cả hai và xét đoạn trong; nếu khác nhau, phải thêm một ký tự vào đầu hoặc cuối, thử cả hai cách và lấy nhỏ nhất cộng 1. Không nhớ kết quả nên chạy chậm khi xâu dài. Nếu chỉ nộp sub này: đúng 3/20 test.
Sub 2: Quy hoạch động theo đoạn — ~O(n^2)~
Lưu ~f[l][r]~ theo độ dài đoạn tăng dần: nếu ~S[l] = S[r]~ thì ~f[l][r] = f[l+1][r-1]~, ngược lại ~f[l][r] = 1 + \min(f[l+1][r], f[l][r-1])~. Với ~n \le 1000~ chạy rất nhanh. Nộp riêng sub này đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc cả dòng xâu (bỏ ký tự xuống dòng thừa); nếu ~n \le 20~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chương trình đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
string s;
int n;
static int f[1005][1005];
// Sub 1: đệ quy không nhớ — thử thêm ký tự ở đầu hoặc cuối, O(2^n), dùng khi n <= 20
int rec(int l, int r) {
if (l >= r) return 0;
if (s[l] == s[r]) return rec(l + 1, r - 1);
return 1 + min(rec(l + 1, r), rec(l, r - 1));
}
void sub1() {
cout << rec(0, n - 1) << "\n";
}
// Sub 2: quy hoạch động theo đoạn [l, r], O(n^2)
void sub2() {
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
if (s[l] == s[r]) f[l][r] = (len == 2 ? 0 : f[l + 1][r - 1]);
else f[l][r] = 1 + min(f[l + 1][r], f[l][r - 1]);
}
cout << f[0][n - 1] << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
getline(cin, s);
while (!s.empty() && (s.back() == '\r' || s.back() == '\n')) s.pop_back();
n = s.size();
if (n == 0) { cout << 0 << "\n"; return 0; }
if (n <= 20) sub1();
else sub2();
return 0;
}
Bình luận