제출 #384437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384437		ogibogi2004	Lamps (JOI19_lamps)	C++14	100 / 100	504 ms	72952 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+6;
int dp[MAXN][4][4];
/*
 * 0 - nothing
 * 1 - flip
 * 2 - 0
 * 3 - 1
*/
int a[MAXN],b[MAXN];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		a[i]=c-'0';
	}
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		b[i]=c-'0';
	}
	for(int i=0;i<MAXN;i++)
	{
		for(int i1=0;i1<4;i1++)
		for(int i2=0;i2<4;i2++)
		{
			dp[i][i1][i2]=MAXN+1;
		}
	}
	dp[0][0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int i1=0;i1<4;i1++)
		for(int i2=0;i2<4;i2++)
		{
			if(i1==0&&i2!=0)continue;
			int a1=a[i];
			if(i1==1)a1=1-a1;
			if(i1==2)a1=0;
			if(i1==3)a1=1;
			if(i2==1)a1=1-a1;
			if(i2==2)a1=0;
			if(i2==3)a1=1;
			if(a1!=b[i])continue;
			dp[i][i1][i2]=min(dp[i][i1][i2],dp[i-1][i1][i2]);
			for(int j=0;j<4;j++)dp[i][i1][i2]=min(dp[i][i1][i2],dp[i-1][i1][j]+(i2>0));
			for(int j=0;j<4;j++)dp[i][i1][i2]=min(dp[i][i1][i2],dp[i-1][j][i1]+(i2>0));
			for(int j=0;j<4;j++)dp[i][i1][i2]=min(dp[i][i1][i2],dp[i-1][i2][j]+(i1>0));
			for(int j=0;j<4;j++)dp[i][i1][i2]=min(dp[i][i1][i2],dp[i-1][j][i2]+(i1>0));
			for(int j1=0;j1<4;j1++)for(int j2=0;j2<4;j2++)dp[i][i1][i2]=min(dp[i][i1][i2],dp[i-1][j1][j2]+(i1>0)+(i2>0));
		}
		/*cout<<i<<":\n";
		for(int i1=0;i1<2;i1++)
		for(int i2=0;i2<2;i2++)
		for(int i3=0;i3<2;i3++)
		{
			cout<<i1<<" "<<i2<<" "<<i3<<" "<<dp[i][i1][i2][i3]<<endl;
		}*/
	}
	int ans=MAXN;
	for(int i1=0;i1<4;i1++)
	for(int i2=0;i2<4;i2++)
	{
		ans=min(ans,dp[n][i1][i2]);
	}
	cout<<ans<<endl;
return 0;
}

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