题意

给定长度为 $N$ ($1\le N\le 10^6$) 的 $01$ 串 $S$。你可以进行下列三种操作：

• 将 $S$ 的一个子串变为全 $0$。
• 将 $S$ 的一个子串变为全 $1$。
• 将 $S$ 的一个子串取反。

用最少的步数将 $S$ 变为另一个给定的 $01$ 串 $T$。

题解

首先，可以将所有取反的操作放在最后执行。那么在执行完所有前两种操作后，假设当前串为 $S'$，则需要的取反操作的次数为 $S'\oplus T$ 的差分数列中 $1$ 的个数。由于前两种操作选择的子串一定不相交，那么从前往后枚举每个数的决策，简单 dp 即可。

时间复杂度：$O(N)$。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
constexpr int INF = 1e9;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::string s, t;
    std::cin >> s >> t;
    s = '0' + s + '0';
    t = '0' + t + '0';
    std::vector dp{0, INF, INF};
    auto f = [&](int b, int x) {
        if (x == 0) {
            return b;
        } else if (x == 1) {
            return 0;
        } else {
            return 1;
        }
    };
    for (int i = 1; i <= n + 1; ++i) {
        std::vector newDp{INF, INF, INF};
        for (int x = 0; x < 3; ++x)
            for (int y = 0; y < 3; ++y)
                newDp[y] = std::min(newDp[y], dp[x] + (x && x != y) + (y && x != y) + (f(s[i - 1] - '0', x) ^ t[i - 1] ^ f(s[i] - '0', y) ^ t[i]));
        dp = newDp;
    }
    std::cout << dp[0] / 2 << "\n";
    return 0;
}