[STEP5][DP] 0004 Ch1-1.一切的開始

#include<stdio.h>

#include<algorithm>

using namespace std;

char s[10000005];

int dp[10000005][2];

int main(){

    int n,i;

    scanf("%d\n",&n);

    gets(s);

    if(s[0]=='1') dp[0][0]=1;

    else dp[0][1]=1;

    for(i=1;s[i];i++){

        if(s[i]=='1'){

            dp[i][1]=dp[i-1][1];

            dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+1);

        }

        else{

            dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]+1);

            dp[i][0]=dp[i-1][0];

        }

    }

    printf("%d\n",dp[n-1][1]);

}