Submission #1291106

#TimeUsernameProblemLanguageResultExecution timeMemory
1291106simona1230Lamps (JOI19_lamps)C++20
4 / 100
59 ms48504 KiB
#include <bits/stdc++.h>

using namespace std;

int dp[1000001][10];
vector<int> v[10]={{},{1},{1,2},{1,3},{1,2,3},{1,3,2},{2},{3},{2,3},{3,2}};

int n;
string s;
int a[1000001];
int b[1000001];
int add[11][11];

void read()
{
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10;j++)
        {
            int h=0;
            while(h<v[i].size()&&h<v[j].size()&&v[i][h]==v[j][h])
                h++;
            add[i][j]=v[j].size()-h;
        }
    }
    cin>>n>>s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='0')a[i+1]=3;
        else a[i+1]=2;
    }

    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='0')b[i+1]=3;
        else b[i+1]=2;
    }

    for(int i=0;i<10;i++)
    {
        dp[1][i]=1e9;
        if(v[i].size()&&b[1]==v[i][v[i].size()-1])
            dp[1][i]=v[i].size();
    }
    if(a[1]==b[1])dp[1][0]=0;
    else dp[1][1]=1;

    for(int i=2;i<=n;i++)
    {
        if(a[i]==b[i])
        {
            dp[i][0]=1e9;
            for(int j=0;j<10;j++)
                dp[i][0]=min(dp[i][0],dp[i-1][j]);
            dp[i][1]=1e9;
        }
        else
        {
            dp[i][1]=1e9;
            for(int j1=0;j1<10;j1++)
                dp[i][1]=min(dp[i-1][j1]+add[j1][1],dp[i][1]);
            dp[i][0]=1e9;
        }

        for(int j=2;j<10;j++)
        {
            if(b[i]!=v[j][v[j].size()-1])
            {
                dp[i][j]=1e9;
                continue;
            }

            dp[i][j]=1e9;
            for(int j1=0;j1<10;j1++)
            {
                dp[i][j]=min(dp[i-1][j1]+add[j1][j],dp[i][j]);
            }
        }

        /*for(int j=0;j<10;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;*/
    }

    int ans=n;
    for(int i=0;i<10;i++)
        ans=min(ans,dp[n][i]);
    cout<<ans<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	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...