程序查找成本，以便在C ++中删除具有成本的连续重复字符？

假设我们有一个包含小写字母的字符串，并且还有一个名为cost的非负值列表，该字符串和列表的长度相同。我们可以删除成本s [i]的字符s [i]，然后同时删除s [i]和costs [i]。我们必须找到删除所有连续重复的字符的最低费用。

因此，如果输入像s =“ xxyyx” nums = [2，3，10，4，6]，那么输出将是6，因为我们可以删除s [0]和s [3]的总成本2 + 4 = 6。

为了解决这个问题，我们将按照以下步骤

• 定义一个堆栈st

• 费用：= 0

• 对于初始化i：= 0，当i <s的大小时，进行更新（将i增加1），请执行以下操作：

• 推我到圣

• 如果nums [st of top]> nums [i]，则：

• 除此以外：

• 费用：=费用+数字[i]

• 费用：=费用+数字[顶部]

• 来自st的pop元素

• 推我到圣

• 如果st的大小不为0并且s [top of st]与s [i]相同，则：

• 除此以外

• 返回成本

让我们看一下下面的实现以获得更好的理解

示例

#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}

输出结果

6