题目描述
牛妹正在玩一个数列
他手里有一个长度为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;
}