dp により前からのみ文字列を扱う方法を解説します。

問題の性質を利用して前後から文字列を扱う方法はこちらで紹介しています。

\(dp_{i,j,k}\) を \(S\) の \(1\) 文字目から \(i\) 文字目までを (\(i\) 文字目まででの) 隣接する文字が同じであるものが \(j\) 箇所であり、\(i\) 文字目が \(k\) であるような文字列に置き換えるために必要なコストの最小値として定義します（\(k\) の値では 0 や 1 を単に整数の \(0\) や \(1\) と同様に扱っていることに注意してください）。

答えは \(\min(dp_{N,1,0}, dp_{N,1,1})\) です。

\(dp_{i,j,k}\) の具体的な計算について説明します。

説明の簡略化のため、\(k = 0\) とします。\(k = 1\) でも同様に計算できます。

\(i - 1\) 文字目の文字に注目して場合分けを行います。

\(i - 1\) 文字目の文字が 0 であるときは \(i -1\) 文字目と \(i\) 文字目が一致しており、\(i - 1\) 文字目の文字が 1 であるときは \(i-1\) 文字目と \(i\) 文字目が一致していません。

したがって、\(S_i =\) 0 のとき \(dp_{i,j,0} = \min(dp_{i-1,j-1,0}, dp_{i-1,j,1})\)、\(S_i =\) 1 のとき \(dp_{i,j,0} = \min(dp_{i-1,j-1,0}, dp_{i-1,j,1} )+ C_i\) です（\(j = 0\) のときは \(j - 1\) は負になるので、その際は min を取る対象から外してください）。

\(j \leq 1\) であるもののみ管理すればよいため dp の状態数は \(O(N)\) 個でよく、遷移は \(O(1)\) 通りであるため答えは時間計算量 \(O(N)\) で計算できます。

実装例

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