版权声明：本文为“牛哄哄的柯南”原创文章，经原创者同意后编写！
原文链接：https://blog.csdn.net/weixin_43883917/article/details/108133529
题目链接:牛妹爱数列
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述:
牛妹正在玩一个数列
他手里有一个长度为n的序列a，保证它是一个01序列，并执行以下两种操作：
1.单点修改：将位置x上的数翻转（0变1,1变0）；
2.前缀修改：将位置1~x上的数翻转（每个数都0变1,1变0）。
他现在想要最小化翻转次数，使得数列上的所有数都变为0。
输入描述:
第一行，输入一个数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
备注:
数据保证1<= n <=10^5,0<= ai <=1。
题意：就是求把所有的数翻转成0的最小翻转数。
思路：就是dp关键是写出状态转移方程即可。
dp[i][0]表示[1,i]全部翻转成0所需的最小翻转次数
dp[i][1]表示[1,i]全部翻转成0所需的最小翻转次数
定义数组a存n个数
如果a[i] == 1 ，状态转移方程：
dp[i][0] = min（[1,i-1] 区间变成0的最小次数在加上把a[i]这个1翻成0的这一步，把[1,i-1] 区间翻成1的最小次数（此时[1,i]区间全是1）
然后把[1,i]这个区间翻转，次数加1）
dp[i][1] = min（[1,i-1]翻成0的最小次数，然后我再多一步把[1,i-1]区间翻一下，因为a[i]为1，所以此时[1,i]就都是1了，
因为a[i]就是1，所以，次数就与[1,i-1]翻成1的次数相等）
其实a[i]==0 的状态转移方程可以由上面思想一样，为了更好理解，我在此就再细说一遍
如果a[i] == 0 ，状态转移方程：
dp[i][0] = min（因为a[i]=0,所以与区间[1,i-1]翻成0的次数相等，把区间[1,i-1]翻成1的次数多一步，
把区间[1,i-1]整体翻一下，这时[1,i]就都是0了）
dp[i][1] = min（区间[1,i-1]翻成0的次数，此时[1,i]就都是0，然后再把区间[1,i]翻一下，就全变成1了，
区间[1,i-1]翻成1的步数，再加上把a[i]这个0翻成1的这一步）
最后输出区间[0,n]全变成0的最下次数，也就是dp[n,0]即可。
代码：
#include
using namespace std;
const int maxn=1e5+5;
int dp[maxn][2],a[maxn];
int main()
{
int n;
while(cin>>n)
{
memset(dp,0,sizeof(a));
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
if(a[i]) // a[i] == 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 // a[i] == 0
{
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);
}
}
cout<
加油！
共同努力！
Keafmd
强力驱动