Chuyển đổi trọng số tối đa của một chuỗi nhất định trong C ++

Tuyên bố vấn đề

Cho một chuỗi chỉ bao gồm A và B. Chúng ta có thể biến đổi chuỗi đã cho thành một chuỗi khác bằng cách chuyển đổi bất kỳ ký tự nào. Do đó có thể thực hiện được nhiều phép biến đổi của chuỗi đã cho. Nhiệm vụ là tìm Trọng lượng của phép biến đổi trọng lượng lớn nhất.

Trọng lượng của vết đốt được tính theo công thức dưới đây -

Weight of string = Weight of total pairs + weight of single characters - Total number of toggles.

• Hai ký tự liên tiếp chỉ được coi là một cặp nếu chúng khác nhau.

• Trọng lượng của một cặp (cả hai ký tự đều khác nhau) =4

• Trọng lượng của một ký tự =1

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

• Các phép biến đổi của chuỗi đã cho là "AA", "AB", "BA" và "BB".

• Chuyển đổi trọng lượng tối đa là "AB" hoặc "BA". Và trọng lượng là "Một cặp - Một chuyển đổi" =4-1 =3.

Thuật toán

1. If (n == 1)
   maxWeight(str[0..n-1]) = 1
2. Else If str[0] != str[1]
   maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1])
3. Elses
   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 << "Result = " << getMaxWeight(str) << endl;
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Result = 3