Python에서 부분 문자열을 제거하여 최대 점수를 계산하는 프로그램

<시간/>

문자열 s와 두 개의 값 x와 y가 있다고 가정합니다. 주어진 두 가지 유형의 작업을 여러 번 수행할 수 있습니다.

검색 하위 문자열 "ab"가 있는 경우 제거하여 x점을 얻을 수 있습니다.
검색 하위 문자열 "ba"가 있는 경우 제거하여 y점을 얻을 수 있습니다.

위의 연산을 s에 적용한 후 얻을 수 있는 최대 포인트를 찾아야 합니다.

따라서 입력이 s ="cbbaacdeabb" x =4 y =5와 같으면 초기 문자열이 "cbbaacdeabb"이므로 출력은 14가 되고 "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이면
- 와 b 교환
- x와 y 교체
s의 각 c에 대해
- c가 다음과 같으면
  - a_st :=a_st + 1
- 그렇지 않고 c가 b와 같을 때
  - a_st가 0이 아니면
    - 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))

입력

"cbbaacdeabb", 4, 5