การแปลงน้ำหนักสูงสุดของสตริงที่กำหนดใน C++

คำชี้แจงปัญหา

ให้สตริงที่ประกอบด้วย A และ B เท่านั้น เราแปลงสตริงที่กำหนดเป็นสตริงอื่นได้โดยสลับอักขระใดก็ได้ ดังนั้นการแปลงสตริงที่กำหนดจำนวนมากจึงเป็นไปได้ ภารกิจคือการหาน้ำหนักของการเปลี่ยนแปลงน้ำหนักสูงสุด

น้ำหนักของเหล็กไนคำนวณโดยใช้สูตรด้านล่าง −

น้ำหนักของสตริง =น้ำหนักของคู่ทั้งหมด + น้ำหนักของอักขระเดี่ยว - จำนวนการสลับทั้งหมด

อักขระสองตัวต่อเนื่องกันถือเป็นคู่ก็ต่อเมื่อต่างกันเท่านั้น
น้ำหนักของคู่เดียว (อักขระทั้งสองต่างกัน) =4
น้ำหนักของอักขระตัวเดียว =1

หากสตริงอินพุตเป็น − "AA" เอาต์พุตจะเป็น 3 −

การแปลงสตริงที่กำหนดคือ "AA", "AB", "BA" และ "BB"
การแปลงน้ำหนักสูงสุดคือ "AB" หรือ "BA" และน้ำหนักคือ "หนึ่งคู่ - หนึ่งสลับ" =4-1 =3

อัลกอริทึม

<ก่อน>1. ถ้า (n ==1) maxWeight(str[0..n-1]) =12. อย่างอื่น ถ้า str[0] !=str[1] maxWeight(str[0..n-1]) =สูงสุด (1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1])3. อื่น maxWeight(str[0..n-1]) =สูงสุด (1 + maxWeight( str[1..n-1]), 3 + getMaxRec(str[2..n-1])

ตัวอย่าง

#includeใช้เนมสเปซ 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, ค้นหา); if (i + 1 ผลลัพธ์ เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 ผลลัพธ์ =3