Hiểu bài toán

Bài toán yêu cầu tìm số bước tối thiểu để biến đổi một chuỗi ký tự S chỉ chứa các ký tự 'A' và 'B' thành một chuỗi 'dạng đặc biệt'. Từ các giải pháp đã nộp, có thể suy luận 'chuỗi dạng đặc biệt' là chuỗi chỉ toàn ký tự 'A' (hoặc có thể chỉ toàn 'B', nhưng các giải pháp đều hướng tới tối ưu cho 'A').

Với mỗi bước biến đổi, ta có thể chọn một ký tự trong chuỗi:

1. Xóa ký tự đó.
2. Thay đổi ký tự đó thành ký tự còn lại ('A' thành 'B' hoặc 'B' thành 'A').

Giá trị của mỗi thao tác này không được đề cập rõ ràng trong đề bài, nhưng các giải pháp cho thấy:

• Chi phí xóa ký tự là 1.
• Chi phí thay đổi ký tự là 2.

Mục tiêu: Tìm tổng chi phí nhỏ nhất để biến S thành chuỗi chỉ chứa 'A'.

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

Cách Quy hoạch động 2 trạng thái (Dynamic Programming)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void solve() {
    string s;
    cin >> s;

    // dpA: chi phí để có một chuỗi toàn 'A' từ các ký tự đã xét
    // dpB: chi phí để có một chuỗi toàn 'B' từ các ký tự đã xét
    long long dpA = 0;
    long long dpB = 0;

    for (char c : s) {
        long long next_dpA, next_dpB;

        if (c == 'A') {
            // Ký tự hiện tại là 'A'
            // Để có chuỗi toàn 'A' ở bước này:
            // - Giữ nguyên 'A' (chi phí 0), lấy state trước đó là A. Hoặc
            // - Đổi 'B' thành 'A' (chi phí 2), lấy state trước đó là B.
            next_dpA = min(dpA, dpB + 2);

            // Để có chuỗi toàn 'B' ở bước này:
            // - Đổi 'A' thành 'B' (chi phí 2), lấy state trước đó là A. Hoặc
            // - Xóa 'A' và giữ chuỗi toàn 'B' trước đó (chi phí 1), lấy state trước đó là B.
            // Lưu ý: Logic này hơi khác một chút so với mô tả chuẩn của bài toán xóa/sửa, nhưng nó là cách các giải pháp thực hiện để tính toán state B.
            // Thực tế, state B ở đây có thể hiểu là: chi phí để có chuỗi toàn 'B' nếu ta bắt buộc phải xử lý ký tự này.
            // Một cách hiểu khác: state B là chi phí 'tạm thời' để dùng cho bước sau.
            next_dpB = min(dpB + 1, dpA + 1); // Chi phí xóa
        } else { // c == 'B'
            // Ký tự hiện tại là 'B'
            // Để có chuỗi toàn 'A': Đổi 'B' thành 'A' (chi phí 2) hoặc Xóa 'B' (chi phí 1).
            next_dpA = min(dpA + 1, dpB + 1);

            // Để có chuỗi toàn 'B': Giữ nguyên 'B' (chi phí 0) hoặc Đổi 'A' thành 'B' (chi phí 2).
            next_dpB = min(dpB, dpA + 2);
        }

        dpA = next_dpA;
        dpB = next_dpB;
    }

    cout << dpA << endl; 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("TRANSTR.INP", "r", stdin);
    freopen("TRANSTR.OUT", "w", stdout);
    solve();
    return 0;
}

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

Giải pháp này sử dụng quy hoạch động với 2 biến lưu trạng thái: dpA và dpB.

• dpA: Chi phí tối thiểu để biến các ký tự đã duyệt thành một chuỗi chỉ chứa 'A'.
• dpB: Chi phí tối thiểu để biến các ký tự đã duyệt thành một chuỗi chỉ chứa 'B'.

Với mỗi ký tự mới, ta cập nhật lại 2 trạng thái này dựa trên giá trị của ký tự đó và chi phí của các thao tác:

1. Nếu ký tự là 'A':
   • Để kết thúc bằng 'A', ta có thể đến từ state 'A' cũ (giữ nguyên 'A') hoặc từ state 'B' cũ (đổi 'B' sang 'A' với chi phí 2).
   • Để kết thúc bằng 'B', ta có thể đến từ state 'B' cũ (giữ nguyên 'B') hoặc từ state 'A' cũ (đổi 'A' sang 'B' với chi phí 2). Tuy nhiên, các giải pháp sử dụng một biến cộng thêm (hoặc logic tương tự) để xử lý việc xóa, ở đây ta thấy các giải pháp dùng min(dpB + 1, dpA + 1) cho việc chuyển sang 'B' từ 'A' khi gặp 'A', ngụ ý rằng việc xóa ký tự có chi phí 1.

Cuối cùng, kết quả là dpA (chi phí để có chuỗi toàn 'A').

Cách Quy hoạch động tối giản (2 biến)

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

int n,dp[1000005][2],res;
string s;
signed main()
{
    freopen("TRANSTR.INP","r",stdin); freopen("TRANSTR.OUT","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    n = s.length();
    s = '#' + s;
    for (int i = 1; i <= n; i++)
    {
        if (s[i]=='A')
        {
            dp[i][0] = dp[i-1][0];
            dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + 1;
        }
        else
        {
            dp[i][0] = min(dp[i-1][0],dp[i-1][1]) + 1;
            dp[i][1] = dp[i-1][1];
        }
    }
    cout << dp[n][0];
}

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

Đây là một biến thể của quy hoạch động, sử dụng mảng 2 chiều dp[i][2]. Ý nghĩa:

• dp[i][0]: Chi phí tối thiểu để xử lý i ký tự đầu tiên sao cho kết quả là chuỗi toàn 'A'.
• dp[i][1]: Chi phí tối thiểu để xử lý i ký tự đầu tiên sao cho kết quả là chuỗi toàn 'B'.

Logic cập nhật:

• Nếu s[i] == 'A':
  • dp[i][0] = dp[i-1][0]: Giữ nguyên 'A', chi phí không đổi.
  • dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1: Để có 'B' tại vị trí này, ta phải xóa 'A' (chi phí 1) và giữ trạng thái 'B' trước đó hoặc chuyển từ 'A' sang 'B'.
• Nếu s[i] == 'B':
  • dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + 1: Để có 'A', ta xóa 'B' (chi phí 1).
  • dp[i][1] = dp[i-1][1]: Giữ nguyên 'B'.

Kết quả: In ra dp[n][0] (chi phí cho chuỗi toàn 'A').

Cách Quy hoạch động với mảng (Dynamic Programming Array)

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

const int N = 1e6 + 5;
ll dp[N][2];
string s;

int32_t main() {
    // Fast I/O
    if (fopen("TRANSTR.INP", "r")) {
        freopen("TRANSTR.INP", "r", stdin);
        freopen("TRANSTR.OUT", "w", stdout);
    }
    cin >> s;
    int n = s.length();
    s = '#' + s;

    for (int i = 1; i <= n; i++) {
        if (s[i] == 'A') {
            dp[i][0] = min(dp[i-1][0], dp[i-1][1] + 2); // Giữ A hoặc đổi B->A
            dp[i][1] = min(dp[i-1][1] + 1, dp[i-1][0] + 1); // Xóa A hoặc xóa và giữ B
        } else {
            dp[i][0] = min(dp[i-1][0] + 1, dp[i-1][1] + 1); // Xóa B hoặc xóa và giữ A
            dp[i][1] = min(dp[i-1][1], dp[i-1][0] + 2); // Giữ B hoặc đổi A->B
        }
    }
    cout << dp[n][0];
}

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

Đây là cách tiếp cận chuẩn của Quy hoạch động, rõ ràng nhất về mặt logic chi phí.

dp[i][0]: Chi phí để có chuỗi toàn 'A' sau khi xử lý i ký tự. dp[i][1]: Chi phí để có chuỗi toàn 'B' sau khi xử lý i ký tự.

Công thức truy hồi:

1. Ký tự 'A':
   • Muốn 'A' (state 0): Giữ 'A' (dp[i-1][0]) hoặc đổi 'B' thành 'A' (dp[i-1][1] + 2).
   • Muốn 'B' (state 1): Ta không thể giữ 'A' để thành 'B'. Ta phải xóa 'A' (dp[i-1][0] + 1) hoặc xóa 'A' mà vẫn giữ được state 'B' trước đó (dp[i-1][1] + 1).

1. Ký tự 'B':
   • Muốn 'A' (state 0): Ta phải xóa 'B' (dp[i-1][0] + 1) hoặc xóa 'B' mà vẫn giữ state 'A' trước đó (dp[i-1][1] + 1).
   • Muốn 'B' (state 1): Giữ 'B' (dp[i-1][1]) hoặc đổi 'A' thành 'B' (dp[i-1][0] + 2).

Lưu ý: Logic min(dp[i-1][1] + 1, dp[i-1][0] + 1) cho việc xóa ký tự hiện tại để giữ nguyên trạng thái mong muốn từ bước trước là một cách viết gọn.

Cuối cùng, in dp[n][0] là đáp án.

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

Bài học kinh nghiệm

• Bài toán có thể chia thành các bài toán con: xử lý từng ký tự một cách độc lập và kết quả phụ thuộc vào trạng thái trước đó.
• Có 2 trạng thái cần theo dõi: trạng thái 'chuỗi toàn A' và 'chuỗi toàn B' ở bước hiện tại.
• Các thao tác (Xóa, Đổi) có chi phí cố định (1 và 2), cho phép áp dụng Quy hoạch động tuyến tính.

Lỗi thường gặp

• Quên cập nhật state phụ (state 'B') một cách chính xác, dẫn đến sai lệch chi phí cho các bước tiếp theo.
• Sai lệch trong chi phí thay đổi ký tự (như coi đổi 'A' thành 'B' có chi phí 1 thay vì 2 theo các giải pháp mẫu).
• Xử lý sai trường hợp chuỗi rỗng hoặc chuỗi đầu vào.