제출 #251944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251944		phamhoanghiep	Lamps (JOI19_lamps)	C++14	4 / 100	133 ms	25972 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+1;
int dp[4][maxn];
int a[maxn];
int b[maxn];
// 0: assign 0
// 1: assign 1
// 2: flip
// 3: vohok
signed main() {
	int n;
	string sa;
	string sb;
	cin>>n>>sa>>sb;
	sa="z"+sa;
	sb="z"+sb;
	for(int i=1 ; i<=n ; i++) {
		if(sa[i]=='1') a[i]=1;
		else a[i]=0;
		if(sb[i]=='1') b[i]=1;
		else b[i]=0;
	}
	dp[0][0]=dp[1][0]=dp[2][0]=dp[3][0]=0;
	for(int i=1 ; i<=n ; i++) {
		if(i==1) {
			if(a[i]==b[i]) {
				dp[a[i]][i]=1;
				dp[3][i]=0;
				dp[2][i]=maxn;
				dp[1-a[i]][i]=maxn;
			}
			else {
				dp[1-a[i]][i]=1;
				dp[2][i]=1;
				dp[3][i]=maxn;
				dp[a[i]][i]=maxn;
			}
		}
		else {
			if(a[i]==b[i]) {
				dp[3][i]=min({
							dp[3][i-1],
							dp[2][i-1],
							dp[a[i]][i-1],
							dp[1-a[i]][i-1]
							});
				dp[2][i]=maxn;
				dp[1-a[i]][i]=maxn;
				dp[a[i]][i]=min({
								dp[a[i]][i-1],
								dp[2][i-1]+1,
								dp[3][i-1]+1,
								dp[1-a[i]][i-1]+1
								});
			}
			else {
				dp[3][i]=maxn;
				dp[2][i]=min({
							dp[2][i-1],
							dp[1][i-1]+1,
							dp[0][i-1]+1,
							dp[3][i-1]+1
							});
				dp[a[i]][i]=maxn;
				dp[b[i]][i]=min({
							dp[b[i]][i-1],
							dp[1-b[i]][i-1]+1,
							dp[2][i-1]+1,
							dp[3][i-1]+1
							});	
			}
		}
		
	}
//	for(int i=0 ; i<=3 ; i++) {
//		for(int j=1 ; j<=n ; j++) {
//			if(dp[i][j]==maxn) cout<<"| ";
//			else cout<<dp[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	int ans1=min({dp[0][n],dp[1][n],dp[2][n],dp[3][n]});
	for(int i=1 ; i<=n ; i++) {
		b[i]=1-b[i];
	}
	dp[0][0]=dp[1][0]=dp[2][0]=dp[3][0]=0;
	for(int i=1 ; i<=n ; i++) {
		if(i==1) {
			if(a[i]==b[i]) {
				dp[a[i]][i]=1;
				dp[3][i]=0;
				dp[2][i]=maxn;
				dp[1-a[i]][i]=maxn;
			}
			else {
				dp[1-a[i]][i]=1;
				dp[2][i]=1;
				dp[3][i]=maxn;
				dp[a[i]][i]=maxn;
			}
		}
		else {
			if(a[i]==b[i]) {
				dp[3][i]=min({
							dp[3][i-1],
							dp[2][i-1],
							dp[a[i]][i-1],
							dp[1-a[i]][i-1]
							});
				dp[2][i]=maxn;
				dp[1-a[i]][i]=maxn;
				dp[a[i]][i]=min({
								dp[a[i]][i-1],
								dp[2][i-1]+1,
								dp[3][i-1]+1,
								dp[1-a[i]][i-1]+1
								});
			}
			else {
				dp[3][i]=maxn;
				dp[2][i]=min({
							dp[2][i-1],
							dp[1][i-1]+1,
							dp[0][i-1]+1,
							dp[3][i-1]+1
							});
				dp[a[i]][i]=maxn;
				dp[b[i]][i]=min({
							dp[b[i]][i-1],
							dp[1-b[i]][i-1]+1,
							dp[2][i-1]+1,
							dp[3][i-1]+1
							});	
			}
		}	
	}
	int ans2=min({dp[0][n]+1,dp[1][n]+1,dp[2][n]+1,dp[3][n]+1});
	cout<<min(ans1,ans2);
}

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