小红的华撃串

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

经过猫猫的细心观察发现，如果把字符串中连续的 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[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;
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

from functools import cache
import sys 

sys.setrecursionlimit(114514)
n = int(input())
s = list(map(int, input().strip()))

@cache
# 从 i 位置开始，当前段的数字是 d，还需要 c 个段
# 做两件事：将当前位置纳入本段，然后决定下一个数字的选择
def f(i, d, c):
    global n 
    # 遍历完成
    # 如果还有未划分出的段，则非法
    if i == n:
        return 1145141919810 if c > 1 else 0
    # 未遍历完成，但是已经提前划分出所有段，原串有剩余，则非法
    if c == 0:
        return 1145141919810
    # 枚举下一个数字的选择：
    # 1. 延续当前段
    ans = f(i + 1, d, c)
    # 2. 切换到下一段（当需要更多段时才进行此项）
    if c > 0:
        ans = min(ans, f(i + 1, 1 - d, c - 1))
    # 如果数字不是需要的，那需要增加一次操作
    return ans + (s[i] ^ d)

print(min(f(0, 0, 4), f(0, 1, 4)))

#include<bits/stdc++.h>
using namespace std;
const int maxn = 510;
int n,ans;
string s;
int sum1[maxn],sum0[maxn];
int main()
{
    scanf("%d",&n),ans = n;
    cin >> s,s = ' ' + s;
    for(int i=1;i<=n;i++)
    {
        sum0[i] = sum0[i - 1] + (s[i] == '0');
        sum1[i] = sum1[i - 1] + (s[i] == '1');
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int k=j+1;k<=n;k++)
            {
                int ans1 = sum1[i] + (sum0[j] - sum0[i]) + (sum1[k] - sum1[j]) + (sum0[n] - sum0[k]);
                int ans2 = sum0[i] + (sum1[j] - sum1[i]) + (sum0[k] - sum0[j]) + (sum1[n] - sum1[k]);
                ans = min(ans,min(ans1,ans2));
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}