题解 | #小红的华撃串#

"01" 和 "10" 子串的出现，在离散数学和字符串处理中等价于状态的跃迁（State Transition）。

当定义一个字符串中 count("01") + count("10") == 3 时，其核心几何与结构意义为：该二进制字符串的相邻字符总共发生了恰好 3 次不同的变化。 基于此，一个合法的“华撃串”必定严格由 4 个连续且交替的同字符数据块组成（例如：0...0 -> 1...1 -> 0...0 -> 1...1，反之亦然）。

给定数据规模为 ，存在两种明显的解题路径：

1. 组合与前缀和策略：在 个可用间隙中插桩寻找 3 个分割点，组合数为 。利用前缀和可以在 时间内计算出每段区间的修改代价。总体复杂度为 。对于 ，计算量约为 ，在常规 1 秒时限内可以通过。
2. 有限状态机与动态规划（FSM-DP）：将字符串的遍历视为时间序列上的状态演进。记录当前前缀已经发生了多少次翻转，以及当前的末尾字符。此方案由于满足最优子结构，具有极高的可扩展性。

在此采用 有限状态机动态规划 作为核心推荐方案。 尽管问题规模为 ，允许 的暴力枚举，但采用 DP 方法将原本由于组合爆炸可能引发的多项式时间复杂度直接降维至线性极值。

复杂度分析

• 时间复杂度：。
• 空间复杂度：

代码实现

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

static constexpr int INF = 1e9 + 7;

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

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

    array<array<int, 2>, 4> dp{};
    for (auto& row : dp) row.fill(INF);

    dp[0][0] = (s[0] == '0') ? 0 : 1;
    dp[0][1] = (s[0] == '1') ? 0 : 1;

    for (int i = 1; i < n; i++) {
        array<array<int, 2>, 4> dp1{INF};
        for (auto& row : dp1) row.fill(INF);

        int cost0 = (s[i] == '0') ? 0 : 1;
        int cost1 = (s[i] == '1') ? 0 : 1;

        for (int j = 0; j <= 3; j++) {
            // 状态 1: 当前位填 '0'
            // 方案 A: 从前一个 '0' 延续（不增加跳转）
            if (dp[j][0] != INF) {
                dp1[j][0] = min(dp1[j][0], dp[j][0] + cost0);
            }
            // 方案 B: 从前一个 '1' 跳转过来（增加一次跳转，需 j > 0）
            if (j > 0 && dp[j - 1][1] != INF) {
                dp1[j][0] = min(dp1[j][0], dp[j - 1][1] + cost0);
            }

            // 状态 2: 当前位填 '1'
            // 方案 A: 从前一个 '1' 延续
            if (dp[j][1] != INF) {
                dp1[j][1] = min(dp1[j][1], dp[j][1] + cost1);
            }
            // 方案 B: 从前一个 '0' 跳转过来
            if (j > 0 && dp[j - 1][0] != INF) {
                dp1[j][1] = min(dp1[j][1], dp[j - 1][0] + cost1);
            }
        }

        dp = dp1;
    }

    cout << min(dp[3][0], dp[3][1]) << endl;
}