C++에서 비용이 있는 연속 중복 문자를 제거하는 비용을 찾는 프로그램은 무엇입니까?

<시간/>

소문자로 된 문자열이 있고 비용이라는 음수가 아닌 값의 목록도 있다고 가정하고 문자열과 목록의 길이는 같습니다. costcosts[i]에 대한 문자 s[i]를 삭제할 수 있으며, 그런 다음 s[i]와 cost[i]가 모두 제거됩니다. 연속적으로 반복되는 모든 문자를 삭제하기 위한 최소 비용을 찾아야 합니다.

따라서 입력이 s ="xxyyx" nums =[2, 3, 10, 4, 6]과 같으면 총 비용에 대해 s[0]과 s[3]을 삭제할 수 있으므로 출력은 6이 됩니다. 2 + 4 =6.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

하나의 스택 정의
비용 :=0
initialize i :=0의 경우 i
- st의 크기가 0이 아니고 s[top of st]가 s[i]와 같은 경우:
  - nums[top of st]> nums[i]인 경우:
    - 비용 :=비용 + 숫자[i]
  - 그렇지 않으면:
    - 비용 :=비용 + 숫자[최상위]
    - st
      의 팝 요소
    - i를 st로 푸시
- 그렇지 않으면
  - i를 st로 푸시
반품 비용

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
   int solve(string s, vector<int>& nums) {
      stack<int> st;
      int cost = 0;
      for (int i = 0; i < s.size(); ++i) {
         if (st.size() && s[st.top()] == s[i]) {
            if (nums[st.top()] > nums[i]) {
               cost += nums[i];
            } else {
               cost += nums[st.top()];
               st.pop();
               st.push(i);
            }
         } else {
            st.push(i);
         }
      }
      return cost;
   }
};


int solve(string s, vector<int>& nums) {
   return (new Solution())->solve(s, nums);
}

main(){
   vector<int> v = {2, 3, 10, 4, 6};
   string s = "xxyyx";
   cout << solve(s, v);
}

입력

"xxyyx",{2,3,10,4,6}