โปรแกรมนับคะแนนสูงสุดจากการลบสตริงย่อยใน Python

สมมติว่าเรามีสตริง s และสองค่า x และ y เราดำเนินการได้ 2 ประเภทกี่ครั้งก็ได้

• ค้นหาสตริงย่อย "ab" หากมี เราสามารถรับคะแนน x ได้โดยการลบออก

• ค้นหาสตริงย่อย "ba" หากมี เราสามารถรับคะแนน y ได้โดยการลบออก

เราต้องหาคะแนนสูงสุดที่เราจะได้รับหลังจากใช้การดำเนินการข้างต้นกับ s

ดังนั้น หากอินพุตเป็น s ="cbbaacdeabb" x =4 y =5 ผลลัพธ์จะเป็น 14 เนื่องจากสตริงเริ่มต้นคือ "cbbaacdeabb" จากนั้นลบ "cbbaacde(ab)b" ​​เพื่อให้ได้ 4 ตอนนี้ string คือ " cbbaacdeb" จากนั้นลบ "cb(ba)acdeb" เพื่อรับ 5 เพิ่มเติม ดังนั้นคะแนนปัจจุบัน 4+5 =9 ตอนนี้สตริงคือ "cbacdeb" จากนั้นจึงลบ "c(ba)cdeb" ออกอีกครั้ง เพื่อให้ได้ 5 เป็นปัจจุบัน คะแนน 9+5=14 และสตริงคือ "ccdeb" ตอนนี้ไม่มีอะไรจะลบต่อไป

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• a :='a', b :='b'
• ตอบ :=0, a_st :=0, b_st :=0
• ถ้า y> x แล้ว
  • สลับ a และ b
  • สลับ x และ y
• สำหรับแต่ละ c ใน s ทำ
  • ถ้า c เหมือนกับ a แล้ว
    • a_st :=a_st + 1
  • มิฉะนั้นเมื่อ c เหมือนกับ b แล้ว
    • ถ้า a_st ไม่ใช่ศูนย์ แล้ว
      • อัน :=ans + x
      • a_st :=a_st - 1
    • มิฉะนั้น
      • b_st +=1
  • มิฉะนั้น
    • ans :=ans + y * ขั้นต่ำของ a_st และ b_st
    • a_st :=0
    • b_st :=0
• ส่งคืน ans + y * ขั้นต่ำของ a_st และ b_st

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(s, x, y):
   a = 'a'
   b = 'b'
   ans = 0
   a_st = 0
   b_st = 0
   if y > x:
      a,b = b,a
      x,y = y,x
   for c in s:
      if c == a:
         a_st += 1
      elif c == b:
         if a_st:
            ans += x
            a_st -= 1
         else: b_st += 1
      else:
         ans += y * min(a_st, b_st)
         a_st = 0
         b_st = 0
   return ans + y * min(a_st, b_st)

s = "cbbaacdeabb"
x = 4
y = 5
print(solve(s, x, y))

อินพุต

"cbbaacdeabb", 4, 5

ผลลัพธ์

14