โปรแกรมค้นหาว่าเราจะได้คะแนนสูงสุดเพียงใดโดยลบ 10 หรือ 01 ออกจากสตริงไบนารีใน Python

สมมติว่าเรามีสตริงไบนารี s และสองค่า zero_one และ one_zero ตอนนี้ให้เราพิจารณาการดำเนินการที่เราสามารถลบสตริงย่อย "01" และรับคะแนน zero_one หรือเราสามารถลบสตริงย่อย "10" และรับคะแนน one_zero เราต้องหาจำนวนคะแนนสูงสุดที่เราจะได้รับหลังจากดำเนินการกี่ครั้ง

ดังนั้น หากอินพุตเป็น s ="10100101" zero_one =3 one_zero =2 เอาต์พุตจะเป็น 11 เนื่องจากเราสามารถลบ "01" ได้สามครั้งเพื่อให้ได้ 3*3 =9 คะแนน จากนั้นสตริงที่เหลือคือ 10 เมื่อลบสิ่งนี้เราจะได้ 2 คะแนนรวมเป็น 11

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

• A :=รายการบิตที่กำหนดเป็นสตริงอินพุต

• ถ้า zero_one

  • สลับ zero_one และ one_zero

  • สำหรับผมอยู่ในช่วง 0 ถึงขนาด A ทำ

    • A[i] :=A[i] XOR 1

• ตอบ :=0

• stack :=สแต็คใหม่

• สำหรับแต่ละ x ใน A ทำ

  • ถ้า stack ไม่ว่างและ stack top element

    • ป๊อปจากสแต็ก

    • ans :=ans + zero_one

  • มิฉะนั้น

    • กด x ลงในกอง

• ans :=ans + one_zero * ขั้นต่ำของการเกิด 0 ใน stack และ 1 ใน stack

• กลับมาอีกครั้ง

ตัวอย่าง (Python)

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

คลาสโซลูชัน:def Solve(self, S, zero_one, one_zero):A =list(map(int, S)) if zero_one  
อินพุต
 
"10100101", 3, 2
 
ผลลัพธ์
 
11