Chương trình tính điểm tối đa từ việc xóa chuỗi con trong Python

Giả sử chúng ta có một chuỗi s và hai giá trị x và y. Chúng tôi có thể thực hiện hai loại hoạt động nhất định bất kỳ lúc nào.

• Tìm kiếm chuỗi con "ab", nếu có, thì chúng ta có thể nhận được x điểm bằng cách xóa nó.

• Tìm kiếm chuỗi con "ba", nếu có, thì chúng ta có thể đạt được y điểm bằng cách loại bỏ nó.

Chúng ta phải tìm ra điểm tối đa mà chúng ta có thể đạt được sau khi áp dụng các thao tác trên trên s.

Vì vậy, nếu đầu vào là s =​​"cbbaacdeabb" x =4 y =5, thì đầu ra sẽ là 14 vì chuỗi ban đầu là "cbbaacdeabb", sau đó xóa "cbbaacde (ab) b" để nhận được 4, bây giờ là chuỗi " cbbaacdeb ", sau đó xóa" cb (ba) acdeb "để có thêm 5, vì vậy điểm hiện tại 4 + 5 =9, chuỗi bây giờ là" cbacdeb ", sau đó lại xóa" c (ba) cdeb ", để có thêm 5 nên hiện tại điểm 9 + 5 =14 và chuỗi là "ccdeb", bây giờ không có gì để xóa tiếp theo.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• a:='a', b:='b'
• ans:=0, a_st:=0, b_st:=0
• nếu y> x, thì
  • hoán đổi a và b
  • hoán đổi x và y
• đối với mỗi c trong s, thực hiện
  • nếu c giống với a, thì
    • a_st:=a_st + 1
  • ngược lại khi c giống với b thì
    • nếu a_st khác 0, thì
      • ans:=ans + x
      • a_st:=a_st - 1
    • nếu không,
      • b_st + =1
  • nếu không,
    • ans:=ans + y * tối thiểu là a_st và b_st
    • a_st:=0
    • b_st:=0
• trả về ans + y * tối thiểu là a_st và b_st

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

"cbbaacdeabb", 4, 5

Đầu ra

14