การแปลงน้ำหนักสูงสุดของสตริงที่กำหนดใน 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. Else
       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