Hướng dẫn giải của KS Câu 4: Xóa xâu
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
Mỗi thao tác xóa một xâu con (liên tiếp) đối xứng; sau khi xóa hai phần còn lại ghép lại với nhau. Tìm số thao tác ít nhất để xóa hết xâu ~S~ (~|S| \le 300~, nhiều bộ dữ liệu).
Sub 1: Vét cạn có nhớ — dùng khi ~|S| \le 12~
Thử mọi xâu con đối xứng để xóa, gọi đệ quy trên xâu còn lại, nhớ kết quả bằng map. Số trạng thái tăng rất nhanh khi xâu dài. Nếu chỉ nộp sub này: đúng 5/6 test.
Sub 2: Quy hoạch động khoảng — ~O(n^3)~
Gọi ~dp[l][r]~ là số thao tác ít nhất để xóa hết ~S[l..r]~. Xét ký tự ~S[l]~: (1) xóa riêng nó: ~1 + dp[l+1][r]~; (2) nếu ~S[l] = S[l+1]~ thì xóa chung hai ký tự này trong một thao tác: ~1 + dp[l+2][r]~; (3) nếu ~S[l] = S[k]~ thì ~S[l]~ và ~S[k]~ là hai đầu của một xâu đối xứng bị xóa cùng lúc, sau khi xóa hết phần giữa: ~dp[l+1][k-1] + dp[k+1][r]~. Lấy nhỏ nhất. Nộp riêng sub này đúng 6/6 test.
Chương trình hoàn chỉnh
Với mỗi bộ dữ liệu, ~main~ gọi sub1 nếu ~|S| \le 12~, 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 6/6 test.
#include <bits/stdc++.h>
using namespace std;
int T;
string s;
int n;
int dp[305][305];
map<string, int> memo;
bool isPal(const string &t) {
string r(t.rbegin(), t.rend());
return r == t;
}
// Sub 1: vét cạn có nhớ — thử xóa mọi xâu con đối xứng, dùng khi |S| <= 12
int brute(const string &t) {
if (t.empty()) return 0;
auto it = memo.find(t);
if (it != memo.end()) return it->second;
int best = 1e9, m = t.size();
for (int l = 0; l < m; l++)
for (int r = l; r < m; r++) {
string u = t.substr(l, r - l + 1);
if (isPal(u)) best = min(best, 1 + brute(t.substr(0, l) + t.substr(r + 1)));
}
return memo[t] = best;
}
void sub1() {
memo.clear();
cout << brute(s) << "\n";
}
// Sub 2: quy hoạch động khoảng O(n^3). dp[l][r] = số thao tác ít nhất để xóa hết s[l..r]
void sub2() {
for (int l = n; l >= 0; l--)
for (int r = l; r < n; r++) {
if (l == r) { dp[l][r] = 1; continue; }
// xóa riêng s[l] (một ký tự là xâu đối xứng)
int best = 1 + dp[l + 1][r];
// s[l] == s[l+1]: xóa cùng nhau
if (s[l] == s[l + 1]) best = min(best, 1 + (l + 2 <= r ? dp[l + 2][r] : 0));
// s[l] == s[k]: s[l] được xóa cùng s[k], phần giữa xóa trước
for (int k = l + 2; k <= r; k++)
if (s[l] == s[k])
best = min(best, dp[l + 1][k - 1] + (k + 1 <= r ? dp[k + 1][r] : 0));
dp[l][r] = best;
}
cout << dp[0][n - 1] << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> T;
while (T--) {
cin >> s;
n = s.size();
if (n <= 12) sub1();
else sub2();
}
return 0;
}
Bình luận