题目链接:牛妹爱数列

来源:牛客网
时间限制: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\begin{cases} 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{cases} a[i]==1dp[i][0]=min(dp[i1][0]+1,dp[i1][1]+1);dp[i][1]=min(dp[i1][0]+1,dp[i1][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\begin{cases} 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{cases} a[i]==0dp[i][0]=min(dp[i1][0],dp[i1][1]+1);dp[i][1]=min(dp[i1][0]+1,dp[i1][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;
}

加油!

共同努力!

Keafmd

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


本文转载:CSDN博客