这道题其实很考验思路喵~ 要用到动态规划才能优雅解决呢！

经过猫猫的细心观察发现，如果把字符串中连续的 0 或 1 看作一个“大块”，那么华撃串恰好需要分成 4 个大块 喵！

比如 000110111 可以分成 "000"、"11"、"0"、"111" 这四大块，相邻对数量就是 3 啦（每两个块之间产生一个“01”或“10”）。

是不是觉得 DP 也没那么难啦？来看看猫猫的思路吧：

我们定义两个数组 f1 和 f0，分别表示以 1 开头和以 0 开头的字符串，下标代表当前已经分成了多少个大块。

例如 f1[2] 表示当前前缀已经构成 2 个大块，并且开头是 1，所需要的最少翻转次数。

现在，我们要处理新来的字符 now（0 或 1），并更新各个块数对应的最少代价。转移的关键在于：每次加入一个新字符，要么延续当前块（块数不变），要么开启一个新块（块数 +1），同时需要根据目标字符决定是否需要翻转。

以 f1[4] 为例：在 f1[4] 的状态下，最后一块一定是 0（因为块数为偶数且开头为 1，结尾与开头相反）。

~~如果新来的字符是 0，那么它可以直接接在末尾（不产生新块），从 f1[3] 转移过来时也不需要翻转（因为 f1[3] 最后一位是 1，现在接 0 正好开启新块），而 f1[4] 自己延续的话则要翻转当前字符为 0（代价 now）。

~~如果新来的字符是 1，那么从 f1[3] 转移时就需要把 1 翻成 0（代价 1-now）才能接到 1 后面开启新块，而 f1[4] 自己延续则要把 1 翻成 0（代价 1-now）。

不过仔细分析后会发现，我们其实可以用统一的形式表达：

f1[4] = min(f1[3], f1[4]) + now

这里的 now 是当前字符的值，因为在 f1[4] 中目标字符是 0，翻转代价就是 now（如果当前是 1 则 now=1 代价 1，如果当前是 0 则 now=0 代价 0）。其他状态也是类似的道理，只要记住每个下标对应的目标结尾字符（由奇偶性决定）就好啦！

按照这个思路，我们就能写出所有转移公式。

最后，块数为 1 时，整个前缀就是同一个字符，所以：

f1[1] += 1-now （保持全 1，当前字符如果是 0 就要翻转）

f0[1] += now （保持全 0，当前字符如果是 1 就要翻转）

初始时，f1[1] = f0[1] = 0，其他都设为一个很大的数（比如 1e5）。

遍历完整个字符串后，答案就是 min(f0[4], f1[4]) 喵～

这样就简单多啦！下面是猫猫的代码实现喵！

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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> f1(5, 1e5), f0(5, 1e5);
    //假设目标结果以一和零开头
    f1[1] = f0[1] = 0;
    for (int i = 0; i < n; i++) {
        int now = s[i] - '0';
        if (i > 2) 
        {
            f1[4] = min(f1[3],f1[4])+now;
            f0[4] = min(f0[3],f0[4])+1-now;
        }
        if (i > 1) 
        {
            f1[3] = min(f1[2],f1[3])+1-now;
            f0[3] = min(f0[2],f0[3])+now;
        }
        if (i > 0) 
        {
            f1[2] = min(f1[1],f1[2])+now;
            f0[2] = min(f0[1],f0[2])+1-now;
        }
        f1[1] += 1 - now;
        f0[1] += now;
    }
    cout << min(f0[4], f1[4]);
    return 0;
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/