题目描述(难度中等)

给定一个字符串s和一个整数数组cost,其中cost[i]是从s中删除字符i的代价。
返回使字符串任意相邻两个字母不相同的最小删除成本。
请注意,删除一个字符后,删除其他字符的成本不会改变。

算法

1,我们只需要将每一段连续出现的字符删除到只剩1个。
2.维护遍历sum和max_c,分别表示当前连续字符的总代价,以及其中最大的代价。
3,删除连续的一段时,需要保留代价最大的,故答案累加sum-max_c

C++代码实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+10;
int cost[N];

int main()
{
    string str;
    cin >> str;
    for(int i=0; i<str.size(); i++)
        cin >> cost[i];

    int res = 0;
    int sum = 0;
    int max_c = 0;
    for(int i=0; i<str.size(); i++)
    {
        if (i==0 || str[i]!=str[i-1])
        {
            res += (sum-max_c);
            sum = max_c = cost[i];
        }
        else
        {
            sum += cost[i];
            max_c = max(max_c, cost[i]);
        }
    }
    res += (sum-max_c);
    cout << res << endl;
    return 0;
}