問題の性質を利用して前後から文字列を扱う方法について解説しています。

dp により前からのみ文字列を扱う方法はこちらで紹介しています。

\(T\) の \(i\) 文字目と \(i + 1\) 文字目が一致するような \(i\) を固定します。すると、\(1\) 文字目から \(i\) 文字目および \(i + 1\) 文字目から \(N\) 文字目は ...0101010101... のように 0 と 1 が交互に並ぶ文字列となります。

したがって、各 \(i\) に対して以下の値が計算できればよいです。

• \(S\) の \(1\) 文字目から \(i\) 文字目を 01010101... のような 0 から始まり 0 と 1 が交互に並ぶ文字列にするために必要なコストの総和の最小値

• \(S\) の \(1\) 文字目から \(i\) 文字目を 10101010... のような 1 から始まり 0 と 1 が交互に並ぶ文字列にするために必要なコストの総和の最小値

• \(S\) の \(i + 1\) 文字目から \(N\) 文字目を ...10101010 のような 0 で終わり 0 と 1 が交互に並ぶ文字列にするために必要なコストの総和の最小値

• \(S\) の \(i + 1\) 文字目から \(N\) 文字目を ...01010101 のような 1 で終わり 0 と 1 が交互に並ぶ文字列にするために必要なコストの総和の最小値

上 \(2\) つは \(i\) での計算結果から \(i + 1\) での計算結果が簡単にわかるため \(i\) の昇順、下 \(2\) つは \(i\) での計算結果から \(i - 1\) での計算結果が簡単にわかるため \(i\) の降順に計算することで答えを求めることができます。

具体的に \(1\) 番上に書いたものの計算を例にして説明します。

\(i + 1\) 文字目は \(i + 1\) が奇数のとき 0 に、偶数のとき 1 にするべきですが、これが元の \(S_{i + 1}\) と一致している場合には \(i\) での計算結果と \(i + 1\) での計算結果は一致します。そうでない場合は、\(i\) での計算結果に \(C_{i + 1}\) を足すことにより \(i + 1\) での計算結果が得られます。

実装の際には、0 で終わる / 1 で終わるというような扱いではなく、(\(N\) 文字全体のうちの) 偶数文字目が 0 で奇数文字目が 1 の文字列 / 偶数文字目が 1 で奇数文字目が 0 の文字列というような扱いをすると考えるべきことが減ると考えられます。

実装例

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