FLY ME TO THE MOON

· · 题解

宝宝题。

首先能发现操作一二的推平区间不交。如果两个推平区间有交，如果他们推平的颜色相同，直接合并为同一个更优，对于推平颜色不同的情况，如果一个区间包含另一个区间，那么可以把后者改为区间翻转，操作数不劣，否则两区间有交但不包含，容易发现先操作的区间完全可以不操作交集，移动区间端点到交集一侧不劣。故每个点只会至多被推平一次。

另一个简单的观察是区间翻转一定在推平之后，并且不会翻转两次。那么可以直接 dp。

记 f_{i,0/1/2,0/1} 表示当前操作完前缀，第 i 位受到的操作是先不推平或推平为 0/1，接着不翻转/翻转。转移 trivial，每次只保留能让 a_i 变成 b_i 的操作状态。转移到下一位时更新操作的状态即可。

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 1e6 + 10;
int F[N][3][2], n; char A[N], B[N];
int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> n >> (A + 1) >> (B + 1);
    memset(F, 0x3f, sizeof F);
    F[1][2][0] = 0;
    for (int i = 1; i <= n; i ++) {
        for (int a = 0; a < 2; a ++) for (int b = 0; b < 2; b ++)
            F[i][a][b] = min(F[i][a][b], F[i][2][b]);
        for (int a = 0; a < 3; a ++) 
            F[i][a][1] = min(F[i][a][1], F[i][a][0]);
        for (int a = 0; a < 3; a ++) for (int b = 0; b < 2; b ++) {
            int t = A[i] - '0';
            if (a != 2) t = a;
            t ^= b;
            if (t != B[i] - '0') F[i][a][b] = 1e9;
        }
        for (int a = 0; a < 3; a ++) for (int b = 0; b < 2; b ++)
            F[i + 1][a][b] = F[i][a][b];
        for (int a = 0; a < 2; a ++) for (int b = 0; b < 2; b ++)
            F[i + 1][2][b] = min(F[i + 1][2][b], F[i][a][b] + 1);
        for (int a = 0; a < 3; a ++) for (int b = 0; b < 2; b ++)
            F[i + 1][a][0] = min(F[i + 1][a][0], F[i][a][b] + 1);
    }
    cout << F[n + 1][2][0] << "\n";
    return 0;
}