Chương trình tìm điểm tối đa khi xóa 10 hoặc 01 từ chuỗi nhị phân trong Python

Cho chuỗi nhị phân s, điểm zero_one (xóa "01"), one_zero (xóa "10"). Tìm điểm tối đa sau các phép xóa bất kỳ.

Ví dụ: s="10100101", zero_one=3, → 11 (xóa 3 lần "01" = 9đ, còn "10" xóa thêm = 2đ).

Giải thuật (Stack greedy ưu tiên cặp điểm cao hơn)

1. Nếu zero_one < one_zero: hoán đổi điểm và đảo bit chuỗi (0↔1) → quy về trường hợp ưu tiên "01".
2. Duyệt chuỗi, dùng stack:
   • Nếu stack đỉnh < x (tức "01"): pop, cộng zero_one.
   • Khác: push x.
3. Sau duyệt, stack còn lại dạng 111...000.... Còn có thể xóa cặp "10" → cộng one_zero * min(count(0), count(1)).

Ví dụ minh họa

class Solution:
    def solve(self, S, zero_one, one_zero):
        A = list(map(int, S))
        if zero_one < one_zero:
            zero_one, one_zero = one_zero, zero_one
            A = [b ^ 1 for b in A]
        ans = 0
        stack = []
        for x in A:
            if stack and stack[-1] < x:  # 0 then 1 -> "01"
                stack.pop()
                ans += zero_one
            else:
                stack.append(x)
        ans += one_zero * min(stack.count(0), stack.count(1))
        return ans

ob = Solution()
s = "10100101"
print(ob.solve(s, 3, 2))  # Output: 11

Đầu vào / Đầu ra

Input: "10100101", 3, 2

Output: 11