[普及-]A108433.

题意

给定一个长度为 $n$ 由 0/1 组成的字符串，你可以花费 $1$ 点代价翻转状态，要求在花费最少的情况下使任意一个长度为 $4$ 的区间里 1 的个数不等于 $3$。

思路

对于最少花费的问题，考虑 dp。设 $dp_{i,j}$ 为到第 $i$ 个数，其最后三位当成二进制处理时结果为 $j$。

对于转移...e...不知道该怎么说，简单做个判断成为从原状态转移到该状态时需要的花费，遍历取最小值即可。

代码使用滚动数组优化

#include<bits/stdc++.h> 
using namespace std;
const int INF = 2e9;
int bcnt[16];
int main(){
    for(int i = 0; i < 16; ++i){
        bcnt[i] = __builtin_popcount(i);//预处理 
    }
    int n;
    string s;
    cin >> n >> s;
    if (n < 4){
        cout << 0 << endl;
        return 0;
    }
    int dp[8];
    fill(dp, dp + 8, INF);
    for(int mask = 0; mask < 8; mask ++){
        int use = 0;
        if(((mask >> 2) & 1) != (s[0] - '0')) use++;
        if(((mask >> 1) & 1) != (s[1] - '0')) use++;
        if((mask & 1) != (s[2] - '0')) use++;
        dp[mask] = min(dp[mask], use);
    }
    for(int i = 3; i < n; ++i){
        int ndp[8];//滚动数组 
        fill(ndp, ndp + 8, INF);
        int cur = s[i] - '0';
        for(int mask = 0; mask < 8; ++mask){
            if(dp[mask] == INF) continue;//选择1或是0 
            for(int d = 0; d <= 1; d ++){
                int four = (mask << 1) | d;
                if (bcnt[four] == 3) continue;
                int new_mask = ((mask << 1) & 7) | d;
                int add = (d != cur) ? 1 : 0;
                ndp[new_mask] = min(ndp[new_mask], dp[mask] + add);
            }
        }
        for(int j = 0; j < 8; j ++) dp[j] = ndp[j];//覆盖 
    }
    int ans = INF;
    for(int mask = 0; mask < 8; ++mask) ans = min(ans, dp[mask]);
    cout << ans << endl;
    return 0;
}