题目描述
牛妹正在玩一个数列
他手里有一个长度为n的序列a，保证它是一个01序列，并执行以下两种操作：
1.单点修改：将位置x上的数翻转（0变1,1变0）；
2.前缀修改：将位置1~x上的数翻转（每个数都0变1,1变0）。
他现在想要最小化翻转次数，使得数列上的所有数都变为0。

输入描述:
第一行，输入一个数n。
第二行，输入n个数，第i个数表示a_ia
i
​
。
输出描述:
输出最小翻转次数。

dp应用

当时做的时候没想出来，比赛结束之后看了alan的题解，不禁感叹！！

在此鸣谢Alan~

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

const int N = 100005;
int a[N], dp[N][2], n;
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)
        {
            dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
            dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + 1);
        }
        else
        {
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1);
            dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
        }
    }
    printf("%d\n", dp[n][0]);
    return 0;
}