Submission #918919

#	Time	Username	Problem	Language	Result	Execution time	Memory
918919		ThylOne	Lamps (JOI19_lamps)	C++14	0 / 100	116 ms	106148 KiB

lamp

//####################
//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(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;
    };

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49