Chuyển đổi chuỗi trọng số tối đa trong C++

Đề bài

Cho một chuỗi chỉ chứa các ký tự 'A' và 'B'. Chúng ta có thể chuyển đổi chuỗi cho trước thành một chuỗi khác bằng cách đảo ngược bất kỳ ký tự nào. Do đó, nhiều chuyển đổi của chuỗi cho trước là có thể. Nhiệm vụ là tìm Trọng số của chuyển đổi có trọng số lớn nhất.

Trọng số của một chuỗi được tính bằng công thức sau:

Trọng số chuỗi = Trọng số tổng các cặp + trọng số ký tự đơn - Tổng số lần đảo.

• Hai ký tự liên tiếp được coi là một cặp chỉ khi chúng khác nhau.
• Trọng số của một cặp đơn (cả hai ký tự khác nhau) = 4
• Trọng số của một ký tự đơn = 1

Nếu chuỗi đầu vào là "AA" thì đầu ra sẽ là 3 –

• Các chuyển đổi của chuỗi cho trước là "AA", "AB", "BA" và "BB".
• Chuyển đổi trọng số tối đa là "AB" hoặc "BA". Và trọng số là "Một cặp - Một lần đảo" = 4-1 = 3.

Thuật toán

1. Nếu (n == 1) maxWeight(str[0..n-1]) = 1
2. Ngược lại nếu str[0] != str[1]
   maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1])
3. Ngược lại
   maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 3 + getMaxRec(str[2..n-1]))

Ví dụ

#include<bits/stdc++.h>
using namespace std;
int getMaxRec(string &str, int i, int n, int lookup[]){
    if (i >= n) {
        return 0;
    }
    if (lookup[i] != -1) {
        return lookup[i];
    }
    int ans = 1 + getMaxRec(str, i + 1, n, lookup);
    if (i + 1 < n) {
        if (str[i] != str[i+1]) {
            ans = max(4 + getMaxRec(str, i + 2, n, lookup), ans);
        } else {
            ans = max(3 + getMaxRec(str, i + 2, n, lookup), ans);
        }
    }
    return lookup[i] = ans;
}
int getMaxWeight(string str){
    int n = str.length();
    int lookup[n];
    memset(lookup, -1, sizeof lookup);
    return getMaxRec(str, 0, str.length(), lookup);
}
int main(){
    string str = "AA";
    cout << "Kết quả = " << getMaxWeight(str) << endl;
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên, nó tạo ra đầu ra sau:

Kết quả = 3