题意 给定一个长度为 nnn 由 0/1 组成的字符串，你可以花费 111 点代价翻转状态，要求在花费最少的情况下使任意一个长度为 444 的区间里 1 的个数不等于 333。 思路 对于最少花费的问题，考虑 dp。设 dpi,jdp_{i,j}dpi,j 为到第 iii 个数，其最后三位当成二进制处理时结果为 jjj。 对于转移...e...不知道该怎么说，简单做个判断成为从原状态转移到该状态时需要的花费，遍历取最小值即可。 代码使用滚动数组优化

题目大意 给定一个长度为 nnn 的 01 串，可以通过翻转某一位（0↔10 \leftrightarrow 10↔1）来修改它。要求最终得到的新串满足：任意连续长度为 444 的子串中，111 的个数不能恰好为 333。求最少需要翻转多少次。 题解思路 本题的约束只涉及长度为 4 的相邻窗口，因此可以用“最近若干位作为状态”的线性 DP。设我们从左到右构造目标串 bbb，当决定了当前位置的值后，未来只会和“最近 3 位”共同组成新的长度为 4 的窗口，所以只需记住最后 3 位即可。 用一个 3 位二进制掩码 mask 表示当前已构造前缀的最后 3 盏灯（从左到右依次是更早到更晚）。令 dp[mask] 为构造到当前位置之前的最少翻转次数。处理第 iii 位时，尝试把 bib_ibi 取为 0 或 1： * 若 i≥4i\ge 4i≥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(n)O(n)，空间为 O(1)O(1)O(1)。 最终答案是处理完全部位置后所有 dp[mask] 的最小值。 参考代码