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

輸出

14

更新於：2021年10月6日

瀏覽量：156

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告