Hiểu bài toán

Bài toán yêu cầu tìm số lượng lệnh tối thiểu cần thực hiện để in ra một xâu ký tự cho trước. Có 3 loại lệnh:

• Lệnh in 1 ký tự (ví dụ: 'O', 'X')
• Lệnh in 2 ký tự 'OX'
• Lệnh in 2 ký tự 'XO' Mỗi lệnh chỉ in được một cặp ký tự cụ thể. Ví dụ, lệnh 'OX' chỉ in được chuỗi "OX", không thể in "XO" hay "OO". Ta cần chia xâu đầu vào thành các đoạn, mỗi đoạn có thể in bằng một lệnh, sao cho số lượng lệnh là ít nhất. Ví dụ với xâu "OX", ta có thể dùng 1 lệnh 'OX' (tổng 1 lệnh) hoặc 2 lệnh 'O' và 'X' (tổng 2 lệnh). Đáp án tối ưu là 1.

Các cách tiếp cận

Cách Quy hoạch động (Dynamic Programming)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string s;
    cin >> s;

    // dp[i] là số lệnh tối thiểu để in xâu con s[0...i-1]
    vector<int> dp(n + 1, 1e9);
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        // Dùng lệnh 1 ký tự để in s[i]
        dp[i+1] = min(dp[i+1], dp[i] + 1);

        // Dùng lệnh 2 ký tự nếu có thể
        if (i + 1 < n) {
            if (s[i] == 'O' && s[i+1] == 'X') {
                dp[i+2] = min(dp[i+2], dp[i] + 1);
            } else if (s[i] == 'X' && s[i+1] == 'O') {
                dp[i+2] = min(dp[i+2], dp[i] + 1);
            }
        }
    }

    cout << dp[n] << endl;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng quy hoạch động để giải quyết bài toán một cách chuẩn mực.

• Xây dựng mảng dp trong đó dp[i] là số lệnh tối thiểu để in xâu con s[0...i-1].
• Khởi tạo dp[0] = 0 (không cần lệnh cho xâu rỗng).
• Với mỗi vị trí i, ta có 2 lựa chọn:
  1. Dùng lệnh 1 ký tự cho s[i]: dp[i+1] = min(dp[i+1], dp[i] + 1)
  2. Nếu s[i]s[i+1] là "OX" hoặc "XO", dùng lệnh 2 ký tự: dp[i+2] = min(dp[i+2], dp[i] + 1)
• Đáp án là dp[n].
• Độ phức tạp: O(n) thời gian và O(n) bộ nhớ.

Cách Tham lam (Greedy)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string s;
    cin >> s;

    int ans = 0;

    for (int i = 0; i < n; ) {
        // Kiểm tra xem có thể dùng lệnh 2 ký tự không
        if (i + 1 < n && s[i] != s[i+1]) {
            // "OX" hoặc "XO"
            ans++;
            i += 2; // Bỏ qua 2 ký tự
        } else {
            // Phải dùng lệnh 1 ký tự
            ans++;
            i += 1;
        }
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cách tiếp cận tham lam là tối ưu nhất cho bài toán này.

• Nguyên lý: Nếu có thể dùng lệnh 2 ký tự (tức là "OX" hoặc "XO"), ta nên dùng ngay lập tức. Việc này không bao giờ làm hỏng đáp án tối ưu.
• Lý do: Nếu dùng 2 lệnh 1 ký tự cho "OX", ta tốn 2 lệnh. Nếu dùng 1 lệnh "OX", ta tốn 1 lệnh. Vì vậy, "luôn ưu tiên dùng lệnh 2 ký tự khi có thể" là lựa chọn đúng đắn.
• Thuật toán: Duyệt từ trái sang phải:
  • Nếu s[i] != s[i+1] (tức là "OX" hoặc "XO"), dùng 1 lệnh và nhảy 2 bước.
  • Ngược lại, dùng 1 lệnh cho ký tự hiện tại và nhảy 1 bước.
• Độ phức tạp: O(n) thời gian và O(1) bộ nhớ.

Cách Tham lam (Cải tiến)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    long long n;
    string s;
    cin >> n >> s;

    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        // Kiểm tra "OX" hoặc "XO"
        if ((s[i] == 'O' && s[i+1] == 'X') || (s[i] == 'X' && s[i+1] == 'O')) {
            cnt++;
            i++; // Nhảy qua ký tự tiếp theo
        } else {
            cnt++;
        }
    }

    cout << cnt;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là phiên bản chi tiết hơn của phương pháp tham lam, kiểm tra rõ ràng điều kiện "OX" hoặc "XO".

• Logic tương tự: Duyệt qua từng vị trí, nếu phát hiện "OX" hoặc "XO" thì dùng 1 lệnh cho cả cặp và bỏ qua 2 ký tự.
• Nếu không phải cặp đặc biệt, chỉ dùng 1 lệnh cho 1 ký tự.
• Phiên bản này dễ hiểu nhưng có thể viết gọn hơn bằng cách kiểm tra s[i] != s[i+1].
• Đây cũng là phương pháp tối ưu với O(n) thời gian và O(1) bộ nhớ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có tính chất tham lam: luôn ưu tiên dùng lệnh 2 ký tự (OX hoặc XO) khi có thể vì nó giúp giảm số lệnh so với việc dùng 2 lệnh 1 ký tự.
• Quy hoạch động là một cách tiếp cận tổng quát và an toàn, cho phép giải quyết bài toán ngay cả khi có các ràng buộc phức tạp hơn (ví dụ: chi phí khác nhau cho các loại lệnh).
• Cấu trúc bài toán là chia xâu thành các phần không giao nhau, mỗi phần được xử lý độc lập.

Lỗi thường gặp

• Lỗi truy cập ngoài biên mảng: Khi kiểm tra s[i+1], cần đảm bảo i + 1 < n.
• Nhầm lẫn giữa "OX" và "XO": Cần đảm bảo xử lý đúng cả hai trường hợp này (ký tự khác nhau).
• Bỏ qua trường hợp dùng lệnh 1 ký tự: Ngay cả khi có thể dùng lệnh 2 ký tự, việc chỉ dùng lệnh 1 ký tự cho đến hết vẫn là một lựa chọn hợp lệ (dù không tối ưu).