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

Giả sử ta có một chuỗi s và hai giá trị x, y. Ta có thể thực hiện hai loại thao tác sau bất kỳ số lần:

• Tìm chuỗi con "ab", nếu có, xóa nó để được x điểm.
• Tìm chuỗi con "ba", nếu có, xóa nó để được y điểm.

Ta cần tìm điểm tối đa có thể đạt được sau khi áp dụng các thao tác trên s.

Ví dụ, nếu s = "cbbaacdeabb", x = 4, y = 5, đầu ra sẽ là 14 vì:

• Chuỗi ban đầu: "cbbaacdeabb", xóa "ab" → được 4 điểm, chuỗi thành "cbbaacdeb"
• Xóa "ba" → được 5 điểm, tổng 9, chuỗi thành "cbacdeb"
• Xóa "ba" → được 5 điểm, tổng 14, chuỗi thành "ccdeb"
• Không còn chuỗi con nào để xóa

Giải pháp

Để giải quyết bài toán này, ta thực hiện các bước sau:

• a := 'a', b := 'b'
• ans := 0, a_st := 0, b_st := 0
• Nếu y > x:
  • Hoán đổi a và b
  • Hoán đổi x và y
• Với mỗi ký tự c trong s:
  • Nếu c == a: a_st := a_st + 1
  • Ngược lại nếu c == b:
    • Nếu a_st > 0: ans := ans + x; a_st := a_st - 1
    • Ngược lại: b_st += 1
  • Ngược lại (ký tự khác a,b):
    • ans := ans + y * min(a_st, b_st)
    • a_st := 0; b_st := 0
• Trả về ans + y * min(a_st, b_st)

Ví dụ minh họa

Xem 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