题目

牛妹爱数列

思路

有两种操作：

  • 翻转 这个点。
  • 翻转 一个区间。

想要翻转一个不以 为左端点的区间 只需要两步，先翻转，再翻转即可。
因此想到成块的 可以用区间修改，单个的 可以用单点修改。
考虑以下几种情况

  1. 00111011，把中间的零改成 再区间修改需要 次操作，优于两次区间修改。
  2. 001110011，把中间两个零改成 再区间修改需要 次操作，和两次区间操作相同。
  3. 00111010，把中间的零改成 再区间修改需要 次操作，和一次区间修改加一次单点修改相同。
  4. 001110010，把中间的两个零改成 再区间修改需要 次操作，劣于一次区间修改加一次单点修改。

从以上四种情况总结出先把单个的 都改成 如果最后有两个 的块（长度大于 ，且都是 ） 中间只有一个零就可以先把零改成 再区间修改了。

Code

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 100001

int n, ans, a[MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 1 && i != 1 && a[i - 1] == 0 && a[i + 1] == 0) {
            ++ans;
            a[i] = 0;
        }
        if (a[i] == 0 && a[i - 1] == 1 && a[i + 1] == 1) {
            a[i] = 1;
            ++ans;
        }
    }
    int last = 0;
    for (int i = 1; i <= n; ++i) {
        if (last == 0 && a[i] == 1) {
            last = i;
        }
        if (last != 0 && a[i] ==0) {
            if (last == 1) ++ans;
            else ans += 2;
            last = 0;
        }
    }
    if (last != 0) {
        if (last == 1) ++ans;
        else ans += 2;
        last = 0;
    }
    std::cout << ans << '\n';
    return 0;
}