题解 | 小红的华撃串

看了一眼题解，都是dp做的，其实n<=500的话，直接枚举四个块的位置，然后讨论0101和1010两种情况也能过（

具体每个块里面要操作多少次，可以通过前缀和求出这个块中原本1的个数 x ，如果这块最后要求全0则要操作x次，要求全1则要操作len-x次（len为块的长度）

答案取所有情况的最小值即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using pll = pair<ll, ll>;
#define fp(i, l, r) for(int i=(l); i<=(r); ++i)
#define fq(i, l, r) for(int i=(r); i>=(l); --i)
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << x << '\n';
const int N = 2e5 + 10;
const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;

void init() {

}

void solve() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    vector<ll> pre(n + 1);
    fp(i, 1, n) {
        if (s[i] == '1') pre[i] = pre[i - 1] + 1;
        else pre[i] = pre[i - 1];
    }
    ll ans = 1e10;
    fp(i, 1, n - 3) fp(j, i + 1, n - 2) fp(k, j + 1, n - 1) {
        ans = min(ans, abs(pre[i] - 0) + abs(pre[j] - pre[i] - (j - i)) +
                  abs(pre[k] - pre[j] - 0) + abs(pre[n] - pre[k] - (n - k)));
        ans = min(ans, abs(pre[i] - i) + abs(pre[j] - pre[i] - 0) +
                  abs(pre[k] - pre[j] - (k - j)) + abs(pre[n] - pre[k] - 0));
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int _ = 1;
    // cin>> _;
    while (_--)
        solve();
    return 0;
}