牛妹爱数列（动态规划 dp）

题目链接:牛妹爱数列

来源：牛客网
时间限制：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 ，状态转移方程：

a [ i ] = = 1 { d p [ i ] [ 0 ] = m i n ( d p [ i − 1 ] [ 0 ] + 1 , d p [ i − 1 ] [ 1 ] + 1 ) ; d p [ i ] [ 1 ] = m i n ( d p [ i − 1 ] [ 0 ] + 1 , d p [ i − 1 ] [ 1 ] ) ; 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]); $$\{\begin{array}{l}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]);\end{array}$$

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]);​

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 ，状态转移方程：

a [ i ] = = 0 { d p [ i ] [ 0 ] = m i n ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] + 1 ) ; d p [ i ] [ 1 ] = m i n ( d p [ i − 1 ] [ 0 ] + 1 , d p [ i − 1 ] [ 1 ] + 1 ) ; 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); $$\{\begin{array}{l}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);\end{array}$$

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);​

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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

加油！

共同努力！

Keafmd

本人博客同文链接：牛哄哄的柯南

文章来源: keafmd.blog.csdn.net，作者：牛哄哄的柯南，版权归原作者所有，如需转载，请联系作者。

原文链接：keafmd.blog.csdn.net/article/details/108133529