题解 | #小红的华撃串#

提供一个简单的思路：

理解题意后可见最终状态是如下的其中一种

简而言之就是0块、1块交替，共4个块，两种情况分别考虑即可，此处行文以第一个情况为例。由于，可以接受直接枚举四个块的分界处。不妨将三个分界处记到前三个块的最后一个元素的索引。那么，对于第二个块，代价为 其中，指上0的个数，预处理即可。其他几个块的情况类似。

AC代码:

#include <cassert>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 000 1111 000 1111
// 111 000 111 000

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    assert(n == s.size());
    vector<vector<int>> cnt(2, vector<int>(n, 0));
    cnt[0][0] = s[0] == '0';
    cnt[1][0] = s[0] == '1';
    for (int i = 1; i < n; i++) {
        cnt[0][i] = cnt[0][i - 1] + (s[i] == '0');
        cnt[1][i] = cnt[1][i - 1] + (s[i] == '1');
    }
    auto rangeCnt = [&](int num, int l, int r) {
        assert(num == 0 || num == 1);
        if (l > r) return 0;
        if (l == 0) return cnt[num][r];
        else return cnt[num][r] - cnt[num][l - 1];
    };

    int ans = INT_MAX;
    // i、j、k分别为前三段的最后一个index
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (k == n - 1) continue;
                int cost1 =  (i - 0 + 1 - rangeCnt(0, 0, i)) +
                             (j - (i + 1) + 1 - rangeCnt(1, i + 1, j)) +
                             (k - (j + 1) + 1 - rangeCnt(0, j + 1, k)) +
                             ((n - 1) - (k + 1) + 1 - rangeCnt(1, k + 1, n - 1));
                ans = min(ans, cost1);
                int cost2 = (i - 0 + 1 - rangeCnt(1, 0, i)) +
                            (j - (i + 1) + 1 - rangeCnt(0, i + 1, j)) +
                            (k - (j + 1) + 1 - rangeCnt(1, j + 1, k)) +
                            ((n - 1) - (k + 1) + 1 - rangeCnt(0, k + 1, n - 1));
                ans = min(ans, cost2);
            }
        }
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")