제출 #158549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158549		Mounir	Lamps (JOI19_lamps)	C++14	4 / 100	171 ms	28212 KiB

lamp

#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
using namespace std;

const int TAILLE_CHAINE = 1e6 + 1;
int dp[TAILLE_CHAINE][3][2];
int lenChaine;
bool depart[TAILLE_CHAINE], arrivee[TAILLE_CHAINE];
string d, a;

void litEntree();
void solve();

int main()
{
	litEntree();
	solve();
	return 0;
}

void litEntree()
{
	cin >> lenChaine;
	cin.ignore();
	
	
	getline(cin, d);
	for (int idCara = 0; idCara < lenChaine; ++idCara){
		depart[idCara] = d[idCara] - '0';
	//	cout << depart[idCara];
	}
	
	//cin.ignore();
	getline(cin, a);
	for (int idCara = 0; idCara < lenChaine; ++idCara)
		arrivee[idCara] = a[idCara] - '0';
	for (int i = 0; i < lenChaine; ++i)
		for (int j = 0; j < 3; ++j)
			for (int k = 0; k < 2; ++k)
				dp[i][j][k] = 1e6 + 5;
}

void solve()
{
	for (int idCara = 0; idCara < lenChaine; ++idCara)
	{
		if (idCara == 0)
		{
			if (depart[idCara] == arrivee[idCara])
				dp[idCara][2][0] = 0;
			else
				dp[idCara][2][1] = 1;
			
			dp[idCara][arrivee[idCara]][0] = dp[idCara][arrivee[idCara]][1] =  1;
			dp[idCara][arrivee[idCara]][1]++;
		}
		else
		{
			chmin(dp[idCara][arrivee[idCara]][0], dp[idCara - 1][arrivee[idCara]][0]);
			chmin(dp[idCara][arrivee[idCara]][0], dp[idCara - 1][arrivee[idCara]][1]);
			chmin(dp[idCara][arrivee[idCara]][0], dp[idCara - 1][!arrivee[idCara]][0] + 1);
			chmin(dp[idCara][arrivee[idCara]][0], dp[idCara - 1][!arrivee[idCara]][1] + 1);
			chmin(dp[idCara][arrivee[idCara]][0], dp[idCara - 1][2][0] + 1);
			chmin(dp[idCara][arrivee[idCara]][0], dp[idCara - 1][2][1] + 1);
			
			chmin(dp[idCara][arrivee[idCara]][1], dp[idCara - 1][arrivee[idCara]][0] + 1);
			chmin(dp[idCara][arrivee[idCara]][1], dp[idCara - 1][arrivee[idCara]][1]);
			chmin(dp[idCara][arrivee[idCara]][1], dp[idCara - 1][!arrivee[idCara]][0] + 2);
			chmin(dp[idCara][arrivee[idCara]][1], dp[idCara - 1][!arrivee[idCara]][1] + 1);
			chmin(dp[idCara][arrivee[idCara]][1], dp[idCara - 1][2][0] + 2);
			chmin(dp[idCara][arrivee[idCara]][1], dp[idCara - 1][2][1] + 1);
			
			for (int idDelta = 0; idDelta < 3; ++idDelta)
				for (int idChange = 0; idChange < 2; ++ idChange)
				{
					if (arrivee[idCara] == depart[idCara])
						chmin(dp[idCara][2][0], dp[idCara - 1][idDelta][idChange]);
					else
						chmin(dp[idCara][2][1], dp[idCara - 1][idDelta][idChange] + 1 - idChange);
				}
		}
		
		/*cout << "-------\n";
		for (int i = 0; i < 3; ++i){
			for (int j = 0; j < 2; ++j)
				cout << dp[idCara][i][j] << " ";
			cout << endl;
		}
		cout << "---\n";*/
	}
	
	int mini = 1e6 + 10;
	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 2; ++j)
			chmin(mini, dp[lenChaine - 1][i][j]);
	
	cout << mini << endl;
}

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