Python程序：计算移除子字符串后的最大得分

假设我们有一个字符串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
如果 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 * min(a_st, b_st)
  - a_st := 0
  - b_st := 0
返回 ans + y * min(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

输出

Arnab Chakraborty

更新于：2021年10月6日

浏览量：156

开启你的职业生涯

完成课程获得认证

开始学习