제출 #919108

#제출 시각아이디문제언어결과실행 시간메모리
919108ThylOneLamps (JOI19_lamps)C++14
4 / 100
149 ms106256 KiB
    //####################
    //LAMP-JOI2019
    //####################
    #include<bits/stdc++.h>
     
    using namespace std;
    int n;
    string a,b;
    const int RIEN = 0;
    const int FLIP = 1;
    const int ZERO = 2;
    const int ONE = 3;
    const int ONE_ZERO = 4;
    const int ZERO_ONE = 5;
    const int maxiNode = 1000000;
    int dp[maxiNode][6];
    int solve(int pos,int state){
        if(pos<n && dp[pos][state]!=-1)return dp[pos][state];
        if(pos==n){
            return 0;
        }else{
            int ans = n+1;
            if(state==RIEN){
                ans = min(ans,1+solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            }else if(state == FLIP){
                ans = min(ans, solve(pos+1,FLIP) + (b[pos]==a[pos]?n+1:0));
                ans = min(ans,1+solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
            }else if(state == ZERO){
                ans = min(ans,solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,ZERO_ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            }else if(state == ONE){
                ans = min(ans,solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,1+solve(pos+1,ONE_ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            
            }else if(state == ZERO_ONE){
                ans = min(ans,solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,solve(pos+1,ZERO_ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            }else if(state==ONE_ZERO){
                ans = min(ans,solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,solve(pos+1,ONE_ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            }
            if(a[pos]==b[pos]){
                ans=min(ans, solve(pos+1,RIEN));
            }
            return dp[pos][state]=ans;
        }
    }
    signed main(){
        for(int i = 0;i<maxiNode;i++){
            for(int j = 0;j<6;j++){
                dp[i][j] = -1;
            }
        }
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n;
        cin>>a>>b;
        cout<<solve(0,RIEN)<<endl;
        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...