สมมติว่าเรามีสตริง 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
- ถ้า a_st ไม่ใช่ศูนย์ แล้ว
- มิฉะนั้น
- ans :=ans + y * ขั้นต่ำของ a_st และ b_st
- a_st :=0
- b_st :=0
- ถ้า c เหมือนกับ a แล้ว
- ส่งคืน 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