C++에서 주어진 문자열의 최대 가중치 변환

문제 설명

A와 B로만 구성된 문자열이 주어집니다. 임의의 문자를 토글하여 주어진 문자열을 다른 문자열로 변환할 수 있습니다. 따라서 주어진 문자열의 많은 변형이 가능합니다. 작업은 최대 가중치 변환의 가중치를 찾는 것입니다.

침의 무게는 아래 공식을 사용하여 계산됩니다 -

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

• 두 개의 연속 문자는 서로 다른 경우에만 쌍으로 간주됩니다.

• 한 쌍의 무게(두 문자가 다름) =4

• 단일 문자의 무게 =1

입력 문자열이 − "AA"이면 출력은 3 −

• 주어진 문자열의 변환은 "AA", "AB", "BA" 및 "BB"입니다.

• 최대 중량 변환은 "AB" 또는 "BA"입니다. 그리고 무게는 "One Pair - One Toggle" =4-1 =3입니다.

알고리즘

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])

예시

#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;
}

출력

위 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Result = 3