牛妹爱数列_牛客练习赛67

题目链接：https://ac.nowcoder.com/acm/contest/6885/D

题意

• 给你一个长度为n的仅包含01的序列a，并执行以下操作
• 单点修改：0->1 ，1->0
• 前缀修改：将1~x上的所有点修改
• 问最少操作，使得序列全变0

思路

• 简单dp。
• dp[i][0]表示把1到i的所有点变成0需要的最少操作
• dp[i][1]表示把1到i的所有点变成1需要的最少操作
• 转移方程：
• 
• 
• 当a[i]==0时，dp[i][0]要么前面全是0（dp[i-1][0]），要么前面都是1，然后前缀修改变成0（dp[i-1][1]+1）；dp[i][1]要么前面全是0，前缀修改变成1（dp[i-1][0]+1）,要么前面全是1(dp[i-1][1])，最后需要将第i位的0变成1，所以加一
• 当a[i]==1时，dp[i][0]要么前面全是0（dp[i-1][0]），要么前面都是1，然后前缀修改变成0（dp[i-1][1]+1）；最后需要将第i位的1变成0，所以加一；dp[i][1]要么前面全是0，前缀修改变成1（dp[i-1][0]+1）,要么前面全是1(dp[i-1][1])

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+5;
int dp[maxn][3];
int a[maxn];
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dp[0][0]=dp[0][1]=0;
    for(int i=1;i<=n;i++){
        dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1)+(a[i]==1);
        dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1])+(a[i]==0);
    }
    cout << min(dp[n][0] , dp[n][1] + 1) << endl;
    return 0;
}