算法刷题笔记|牛客网 NC205087 牛妹爱数列区间DP|#

文章目录

1. 题目描述

1.1. Title
1.2. Time Limit
1.3. Memory Limit
1.4. Problem Description
1.5. Input
1.6. Output
1.7. Sample Input
1.8. Sample Output
1.9. Note
1.10. Source

2. 题解
3. 代码

1. 题目描述 1.1. Title
【算法刷题笔记|牛客网 NC205087 牛妹爱数列】牛客网 NC205087 牛妹爱数列
1.2. Time Limit
C/C++ 1秒，其他语言2秒
1.3. Memory Limit
C/C++ 262144K，其他语言524288K
1.4. Problem Description
牛妹正在玩一个数列他手里有一个长度为n的序列a，保证它是一个01序列，并执行以下两种操作：

单点修改：将位置x上的数翻转（0变1,1变0）
前缀修改：将位置1~x上的数翻转（每个数都0变1,1变0）。他现在想要最小化翻转次数，使得数列上的所有数都变为0。

1.5. Input
第一行，输入一个数n n n 。第二行，输入n n n 个数，第i i i 个数表示a i a_i ai?。
1.6. Output
输出最小翻转次数。
1.7. Sample Input

10 1 0 1 1 0 0 0 1 0 0

1.8. Sample Output

3

1.9. Note
数据保证1 ≤ n ≤ 1 0 5 , 0 ≤ a i ≤ 1 1\le n\le 10^5,0\le a_i\le 1 1≤n≤105,0≤ai?≤1。
1.10. Source
牛客网 NC205087 牛妹爱数列
2. 题解题解来自出题人的牛客博客。
考虑动态规划。
我们定义d p [ i ] [ 0 / 1 ] dp[i][0/1] dp[i][0/1] 表示当前第i i i 个位置，将前i i i 个位置全变成0 / 1 0/1 0/1 的最少操作数。
如果当前位置上a [ i ] = 1 a[i]=1 a[i]=1，则：
d p [ i ] [ 0 ] = m i n ( d p [ i ? 1 ] [ 0 ] + 1 , d p [ i ? 1 ] [ 1 ] + 1 ) dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1) dp[i][0]=min(dp[i?1][0]+1,dp[i?1][1]+1)，我们可以将a [ i ] a[i] a[i] 单独翻转，也可以将这前缀1 1 1 一起翻转；
d p [ i ] [ 1 ] = m i n ( d p [ i ? 1 ] [ 1 ] , d p [ i ? 1 ] [ 0 ] + 1 ) dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1) dp[i][1]=min(dp[i?1][1],dp[i?1][0]+1)，我们可以将前缀0 0 0 翻转，然后把a [ i ] a[i] a[i] 拼上去。
如果当前位置上a [ i ] = 0 a[i]=0 a[i]=0 ，则：
d p [ i ] [ 0 ] = m i n ( d p [ i ? 1 ] [ 0 ] , d p [ i ? 1 ] [ 1 ] + 1 ) dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1) dp[i][0]=min(dp[i?1][0],dp[i?1][1]+1)，我们可以将前缀1 1 1 翻转，然后把a [ i ] a[i] a[i] 拼上去；
d p [ i ] [ 1 ] = m i n ( d p [ i ? 1 ] [ 0 ] + 1 , d p [ i ? 1 ] [ 1 ] + 1 ) dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]+1) dp[i][1]=min(dp[i?1][0]+1,dp[i?1][1]+1)，我们可以将a [ i ] a[i] a[i] 单独翻转，也可以将这前缀0一起翻转；
答案记为m i n ( d p [ n ] [ 0 ] , d p [ n ] [ 1 ] ) min(dp[n][0],dp[n][1]) min(dp[n][0],dp[n][1])。
时间复杂度： O ( n ) O(n) O(n)。
3. 代码

#include using namespace std; const int N = 100005; int a[N], dp[N][2] = {0}, n; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> 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; }

联系邮箱：curren_wong@163.com
CSDN：https://me.csdn.net/qq_41729780
知乎：https://zhuanlan.zhihu.com/c_1225417532351741952
公众号：复杂网络与机器学习
欢迎关注/转载，有问题欢迎通过邮箱交流。