We explain a solution that uses DP (Dynamic Programming) and scans the string only from the head.

Another solution that exploits the property of the problem and scans it from the head and tail is introduced here.

Let \(dp_{i,j,k}\) be the minimum cost required to modify the \(1\)-st through \(i\)-th characters of \(S\), so that there are \(j\) pairs of adjacent characters that are the same (within the first \(i\) characters) and the \(i\)-th character becomes \(k\). (Note that 0 and 1 are simply identified with integers \(0\) and \(1\) in the variable \(k\).)

The answer is \(\min(dp_{N,1,0}, dp_{N,1,1})\).

We introduce in detail how to fill \(dp_{i,j,k}\).

For simplicity, we fix \(k = 0\). Those for \(k = 1\) can be done in the same way.

Consider the dependency on the \((i - 1)\)-th character.

If the \((i - 1)\)-th character is 0, the \((i -1)\)-th and \(i\)-th characters are the same; if it is 1, the \((i -1)\)-th and \(i\)-th characters are not the same.

Thus, if \(S_i =\) 0, then \(dp_{i,j,0} = \min(dp_{i-1,j-1,0}, dp_{i-1,j,1})\); if \(S_i =\) 1, then \(dp_{i,j,0} = \min(dp_{i-1,j-1,0}, dp_{i-1,j,1} )+ C_i\). (For \(j = 0\), we have negative \((j - 1)\); in that case, ignore it and take the min of the other values.)

Since we just need to manage those with \(j \leq 1\), so the DP has \(O(N)\) states. The transition costs \(O(1)\) time, so the answer can be found in a total of \(O(N)\) time.

Sample code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll INF = 1'000'000'000'000'000'000;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<ll> c(n);
    for (int i = 0; i < n; i++) cin >> c[i];
    vector dp(n, vector(2, vector(2, INF)));
    dp[0][0][s[0] - '0'] = 0;
    dp[0][0][(s[0] - '0') ^ 1] = c[0];
    for (int i = 1; i < n; i++) {
        int r = s[i] - '0';
        for (int k = 0; k < 2; k++) {
            dp[i][0][k] = dp[i - 1][0][k ^ 1] + (r == k ? 0 : c[i]);
            dp[i][1][k] = min(dp[i - 1][0][k], dp[i - 1][1][k ^ 1]) + (r == k ? 0 : c[i]);
        }
    }
    ll ans = min(dp[n - 1][1][0], dp[n - 1][1][1]);
    cout << ans << '\n';
}