D题的暴力优化：https://ac.nowcoder.com/acm/contest/97443/D

我去后面有点急了就没写出来。发现题解是dp，对于我这种蒟蒻来说还是很难写的。

考虑暴力，令a，b，c分别是把大区间染成0，1，2的前缀和。假设这里把大区间分别染色为 0 1 2，枚举i和j为0和1，1和2的分界点，于是答案为min(a[i]+b[j]-b[i]+c[n]-c[j])。枚举两个点的时间复杂度为O(n2)，考虑优化。

对a[i]+b[j]-b[i]+c[n]-c[j]进行小小的变形，变为：a[i]-b[i], b[j]-c[j], c[n] 求和 (j >= i) 于是可以引用变量记录前面最小的a[i]-b[i],由于j>=i，于是我们可以枚举j。最后加上c[n]就是答案

    rep(j, 1, n) {
        mi = min(a[j] - b[j], mi);
        res = min(res, mi + b[j] - c[j]);
    }
    return res + c[n];

后面暴力枚举六种组合情况，因为都是线性的，所以时间复杂度由O(n2)将为了O(n)。

int get(int n, vector<int> &a, vector<int> &b, vector<int> &c) {
    // a[i]-b[i],b[j]-c[j],c[n] 求和 (j >= i)
    int res = inf, mi = inf;
    rep(j, 1, n) {
        mi = min(a[j] - b[j], mi);
        res = min(res, mi + b[j] - c[j]);
    }
    return res + c[n];
}
void solve() {
    int n;
    cin >> n;
    vector<int> t(n + 1);
    vector<char> c(n + 1);
    rep(i, 1, n) cin >> c[i];
    rep(i, 1, n) cin >> t[i];
    vector<int> a(n + 1), b(n + 1), d(n + 1);
    rep(i, 1, n) a[i] = a[i - 1] + (c[i] == '0' ? 0 : t[i]);
    rep(i, 1, n) b[i] = b[i - 1] + (c[i] == '1' ? 0 : t[i]);
    rep(i, 1, n) d[i] = d[i - 1] + (c[i] == '2' ? 0 : t[i]);
    int res = inf;
    res = min(res, get(n, a, b, d));
    res = min(res, get(n, a, d, b));
    res = min(res, get(n, b, a, d));
    res = min(res, get(n, b, d, a));
    res = min(res, get(n, d, a, b));
    res = min(res, get(n, d, b, a));
    cout << res << '\n';
}