D-牛客爱数列

链接：https://ac.nowcoder.com/acm/contest/6885/D
来源：牛客网

题意：

给你一个长度为n的01序列，你每次能进行下列操作中的一个
1.单点修改：将x位置上的数翻转0变1，1变0
2.前缀修改：将1~x上的数翻转
问你最小的翻转次数

solution：

1.由条件推出，任何数翻转它的偶数次，保持其原来状态不变，否则状态改变
2.如果进行前缀修改，那么对于长度为x的前缀来说，你要贪心的使x,x-1,x-2....上的连续1的个数尽可能大于1
举个例子110101 如果只进行前缀翻转 001010->110100->001000->000000进行了四次翻转，而如果从后往前出现1的连续个数为1进行单点修改，那么110100->110000->000000这样只要进行3次翻转，因此对于连续1的个数大于1才可能形成最优解
因为对连续1的个数为1的进行前缀翻转，会将其前面的0翻转为1，这样你就会增加1次将前面的1翻转会原来0的次数的机会，而如果连续1的个数大于二，最多也就会前缀翻转两次，小于等于将区间的连续翻转的次数
因此我们只要从后往前遍历，对连续1的个数为1的进行单点修改，连续1的个数多于1的进行前缀修改即可

#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int cnt=0,num=0;
    for(int i=n-1;i>=0;i--)
    {
        if((a[i]+cnt)%2==1)
        {
            if(i>0)
            {
                if(a[i-1]==a[i])cnt++;
                else num++;
            }
            else
                num++;
        }
    }
    cout<<cnt+num;
}