官方题解

题目大意

给定一个长度为 $n$ 的 01 串，可以通过翻转某一位（$0 \leftrightarrow 1$）来修改它。要求最终得到的新串满足：任意连续长度为 $4$ 的子串中，$1$ 的个数不能恰好为 $3$。求最少需要翻转多少次。

题解思路

本题的约束只涉及长度为 4 的相邻窗口，因此可以用“最近若干位作为状态”的线性 DP。设我们从左到右构造目标串 $b$，当决定了当前位置的值后，未来只会和“最近 3 位”共同组成新的长度为 4 的窗口，所以只需记住最后 3 位即可。

用一个 3 位二进制掩码 mask 表示当前已构造前缀的最后 3 盏灯（从左到右依次是更早到更晚）。令 dp[mask] 为构造到当前位置之前的最少翻转次数。处理第 $i$ 位时，尝试把 $b_i$ 取为 0 或 1：

• 若 $i\ge 4$，则长度为 4 的窗口正好是“上一状态的 3 位 + 当前选择的 1 位”，对应一个 4 位数 w=(mask<<1)|b_i，若 popcount(w)==3 则该选择非法；
• 否则（前 3 位）没有形成长度为 4 的窗口，不需要检查。

代价增加为 [s_i\ne b_i]，新状态为 ((mask<<1)&7)|b_i。每步转移常数只有 16 次，整体复杂度为 $O(n)$，空间为 $O(1)$。

最终答案是处理完全部位置后所有 dp[mask] 的最小值。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n;
    cin >> s;

    const int INF = 1e9;
    vector<int> dp(8, INF), ndp(8, INF);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        fill(ndp.begin(), ndp.end(), INF);
        int a = s[i] - '0';

        for (int mask = 0; mask < 8; mask++) {
            if (dp[mask] >= INF) continue;

            for (int b = 0; b <= 1; b++) {
                if (i >= 3) {
                    int w = (mask << 1) | b; // 4 bits: last3 + b
                    if (__builtin_popcount((unsigned)w) == 3) continue;
                }
                int cost = dp[mask] + (b != a);
                int nmask = ((mask << 1) & 7) | b;
                if (cost < ndp[nmask]) ndp[nmask] = cost;
            }
        }

        dp.swap(ndp);
    }

    int ans = *min_element(dp.begin(), dp.end());
    cout << ans << "\n";
    return 0;
}