제출 #1222695

#제출 시각아이디문제언어결과실행 시간메모리
1222695AlgorithmWarriorLamps (JOI19_lamps)C++20
100 / 100
90 ms14304 KiB
#include <bits/stdc++.h>

using namespace std;

int const NMAX=1000005;
bool sir1[NMAX],sir2[NMAX];
int dp[NMAX][3];
int n;

void read(){
    cin>>n;
    int i;
    char ch;
    for(i=1;i<=n;++i){
        cin>>ch;
        sir1[i]=ch-'0';
    }
    for(i=1;i<=n;++i){
        cin>>ch;
        sir2[i]=ch-'0';
    }
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

int const INF=1e9;

int get_dp(){
    dp[1][0]=1+(sir2[1]!=0);
    dp[1][1]=1+(sir2[1]!=1);
    dp[1][2]=(sir1[1]!=sir2[1]);
    int i,j,k;
    for(i=2;i<=n;++i)
        for(j=0;j<3;++j){
            dp[i][j]=INF;
            int vj=((j==2)?sir1[i]:j);
            for(k=0;k<3;++k){
                int vk=((k==2)?sir1[i-1]:k);
                minself(dp[i][j],dp[i-1][k]+(j<2 && j!=k)+(vk==sir2[i-1] && vj!=sir2[i]));
            }
        }
    return min(min(dp[n][0],dp[n][1]),dp[n][2]);
}

int main()
{
    read();
    cout<<get_dp();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...