We explain a solution that exploits the property of the problem and scans the string from the head and tail.

Another solution that uses DP (Dynamic Programming) and scans it only from the head is introduced here.

Fix an \(i\) such that the \(i\)-th and \((i + 1)\)-th characters of \(T\) coincide. Then, the \(1\)-st through \(i\)-th and the \((i + 1)\)-th through \(N\)-th characters form ...0101010101..., strings where 0 and 1 appears alternately.

Thus, it is sufficient to find the following values for each \(i\):

• The minimum total cost required to make the \(1\)-st through \(i\)-th characters of \(S\) 01010101..., which starts with 0 and has alternating 0 and 1.

• The minimum total cost required to make the \(1\)-st through \(i\)-th characters of \(S\) 10101010..., which starts with 1 and has alternating 0 and 1.

• The minimum total cost required to make the \((i+1)\)-st through \(N\)-th characters of \(S\) ...10101010, which ends with 0 and has alternating 0 and 1.

• The minimum total cost required to make the \((i+1)\)-st through \(N\)-th characters of \(S\) ...01010101, which ends with 1 and has alternating 0 and 1.

For the former two, the results for \((i + 1)\) can be easily obtained from the result for \(i\), so they can be filled in ascending order of \(i\); for the latter two, those for \((i -1)\) from those for \(i\), so they can be filled in descending order of \(i\).

For example, we introduce how the first value is computed.

The \((i + 1)\)-th character must be made 0 if \((i + 1)\) is odd, and 1 if even; if no modification is needed to do so, the result for \(i\) and that for \((i + 1)\) coincides. Otherwise, one can add \(C_{i + 1}\) to the result for \(i\) to obtain that for \((i + 1)\).

When implementing, instead of considering strings ending with 0 or 1, one can think about a string whose even-positioned characters (among the whole \(N\) characters) are 0 and even-positioned ones are 1, and vice versa, in order to reduce trouble.

Sample code

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

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<ll> f0(n + 1), f1(n + 1), g0(n + 1), g1(n + 1);
    for (int i = 0; i < n; i++) {
        f0[i + 1] = f0[i];
        f1[i + 1] = f1[i];
        if (i % 2 == 0) {
            if (s[i] == '0') f1[i + 1] += c[i];
            else f0[i + 1] += c[i];
        }
        else {
            if (s[i] == '0') f0[i + 1] += c[i];
            else f1[i + 1] += c[i];
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        g0[i] = g0[i + 1];
        g1[i] = g1[i + 1];
        if (i % 2 == 0) {
            if (s[i] == '0') g0[i] += c[i];
            else g1[i] += c[i];
        }
        else {
            if (s[i] == '0') g1[i] += c[i];
            else g0[i] += c[i];
        }
    }
    ll ans = 1'000'000'000'000'000'000;
    for (int i = 1; i < n; i++) ans = min(ans, f0[i] + g0[i]);
    for (int i = 1; i < n; i++) ans = min(ans, f1[i] + g1[i]);
    cout << ans << '\n';
}