题目链接:牛妹爱数列
来源：牛客网
时间限制：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<bits/stdc++.h> 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<<dp[n][0]<<endl; } return 0; }
