用 Python 编写一个程序，计算从删除子字符串中获得的最高分数

pythonserver side programmingprogramming更新于 2025/12/2 18:52:17

假设我们有一个字符串 s 和两个值 x 和 y。我们可以任意多次执行给定的两种类型的操作。

搜索子字符串"ab"，如果存在，则删除它可获得 x 分。
搜索子字符串"ba"，如果存在，则删除它可获得 y 分。

我们必须找到对 s 应用上述操作后可以获得的最高分。

因此，如果输入为 s = "cbbaacdeabb" x = 4 y = 5，则输出将为 14，因为初始字符串为"cbbaacdeabb"，然后删除"cbbaacde(ab)b"得到 4，现在字符串是"cbbaacdeb"，然后删除"cb(ba)acdeb"得到更多的 5，所以当前分数 4+5 = 9，现在字符串是"cbacdeb"，然后再次删除"c(ba)cdeb"，得到额外的 5，所以当前分数 9+5=14，字符串是"ccdeb"，现在没有什么可以删除的了。

为了解决这个问题，我们将遵循以下步骤 −

a := 'a', b := 'b'
ans := 0, a_st := 0, b_st := 0
if y > x，则
- 交换 a 和 b
- 交换 x 和 y
对于 s 中的每个 c，执行
- 如果 c 与 a 相同，则
  - a_st := a_st + 1
- 否则，当 c 与 b 相同时，则
  - 如果 a_st 非零，则
    - ans := ans + x
    - a_st := a_st - 1
  - 否则，
    - b_st += 1
- 否则，
  - ans := ans + y * a_st 和 b_st 的最小值
  - a_st := 0
  - b_st := 0
返回 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))