C ++中给定字符串的最大权重转换
问题陈述
给定一个仅包含A和B的字符串。我们可以通过切换任意字符将给定的字符串转换为另一个字符串。因此，给定字符串的许多转换都是可能的。任务是找到最大权重变换的权重。
ing的重量使用以下公式计算-
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”。权重为“一对-一次切换”=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