牛客练习赛67 D-牛妹爱数列牛客竞赛

牛客练习赛67 D-牛妹爱数列
链接：https://ac.nowcoder.com/acm/contest/6885/D
来源：牛客网
他手里有一个长度为n的序列a，保证它是一个01序列，并执行以下两种操作：
1.单点修改：将位置x上的数翻转（0变1,1变0）；
2.前缀修改：将位置1~x上的数翻转（每个数都0变1,1变0）。
他现在想要最小化翻转次数，使得数列上的所有数都变为0。
链接：https://ac.nowcoder.com/acm/contest/6885/D
来源：牛客网
输入描述:
第一行，输入一个数n。
第二行，输入n个数，第i个数表示ai 。
输出描述:
输出最小翻转次数。
示例1
输入

10 1 0 1 1 0 0 0 1 0 0

输出

3

说明

样例解释：第一次使用（1）操作，把2改掉： 1 1 1 1 0 0 0 1 0 0 第二次使用（2）操作，把1-4全部改掉：
0 0 0 0 0 0 0 1 0 0 第三次使用（1）操作，把8改掉： 0 0 0 0 0 0 0 0 0 0

【牛客练习赛67 D-牛妹爱数列】Code：
定义 dp[i][0/1] 表示当前第ii个位置，将前ii个位置全变成 0/1 的最少操作数。

文章图片

#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long using namespace std; const int INF=0x3f3f3f3f; const double pi=acos(-1.0),eps=1e-8; const ll mod =998244353; const int maxn=1e5+5; int dp[maxn][3]; int main() { int n; scanf("%d",&n); dp[0][0]=0,dp[0][1]=0; for(int i=1; i<=n; i++) { int a; scanf("%d",&a); if(a==1) { dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1); dp[i][1]=min(dp[i-1][0]+1,dp[i-1][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",min(dp[n][0],dp[n][1]+1)); return 0; }