제출 #254156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254156		vjules	Miners (IOI07_miners)	C++14	100 / 100	126 ms	39928 KiB

miners

#include <bits/stdc++.h>
using namespace std;

int longueur;
int type [100001];
int DP [100002][100];

struct Situation	{
	int repasMine1[2];
	int repasMine2[2];
};

inline int SituationToInt (Situation situation)	{
	int repasMine1[2] = {situation.repasMine1[0], situation.repasMine1[1]};;
	int repasMine2[2] = {situation.repasMine2[0], situation.repasMine2[1]};;

	int mine1 = 0;
	if (repasMine1[0] == -1)	{
		repasMine1[0] = repasMine1[1];
	}
	if (repasMine1 [0] == -1)	mine1 = 9;
	else	{
		mine1 = repasMine1[1] + repasMine1[0]*3;
	}

	int mine2 = 0;
	if (repasMine2[0] == -1)	{
		repasMine2[0] = repasMine2[1];
	}
	if (repasMine2 [0] == -1)	mine2 = 9;
	else	{
		mine2 = repasMine2[1] + repasMine2[0]*3;
	}

	return mine2 + mine1*10;
}

inline Situation IntToSituation (int numSituation)	{
	Situation result;
	int mine1 = numSituation/10;
	int mine2 = numSituation%10;

	if (mine1 == 9)	{
		result.repasMine1[0] = -1;
		result.repasMine1[1] = -1;
	}
	else	{
		result.repasMine1[0] = mine1/3;
		result.repasMine1[1] = mine1%3;
	}

	if (mine2 == 9)	{
		result.repasMine2[0] = -1;
		result.repasMine2[1] = -1;
	}
	else	{
		result.repasMine2[0] = mine2/3;
		result.repasMine2[1] = mine2%3;
	}

	return result;
}

inline int nbDiff (int a, int b, int c)	{
	int result = 1;
	if (b != a)	result++;
	if (c != a && c != b)	result++;
	if (a == -1 || b == -1 || c == -1)	result--;
	return result;
}
	





int main() 	{
//	ios:: sync_with_stdio(false);	cin.tie(NULL);	cout.tie(NULL);
	cin >> longueur;
	for (int iElem = 0; iElem < longueur; iElem++)	{
		char lettre;
		cin >> lettre;
		if (lettre == 'M')	type[iElem] = 0;
		else if (lettre == 'F')	type[iElem] = 1;
		else						type[iElem] = 2;
	}
	for (int numSituation = 0; numSituation < 100; numSituation++)	{
		DP[longueur][numSituation] = 0;
	}
	for (int pos = longueur - 1; pos >= 0; pos--)	{
		for (int numSituation = 0; numSituation < 100; numSituation++)	{
			Situation situation1 = IntToSituation(numSituation);
			Situation situation2 = IntToSituation(numSituation);

			int nbDiff1 = nbDiff(situation1.repasMine1[0], situation1.repasMine1[1], type[pos]);
			int nbDiff2 = nbDiff(situation2.repasMine2[0], situation2.repasMine2[1], type[pos]);

			situation1.repasMine1[0] = situation1.repasMine1[1];
			situation2.repasMine2[0] = situation2.repasMine2[1];

			situation1.repasMine1[1] = type[pos];
			situation2.repasMine2[1] = type[pos];

			int scoreDonne1 = DP[pos+1][SituationToInt(situation1)] + nbDiff1;
			int scoreDonne2 = DP[pos+1][SituationToInt(situation2)] + nbDiff2;

			DP[pos][numSituation] = max(scoreDonne1, scoreDonne2);

//			Situation situation = IntToSituation(numSituation);
//			cout << "en " << pos << " avec (" << situation.repasMine1[0] << " " << situation.repasMine1[1] << ")  (" << situation.repasMine2[0] << " " << situation.repasMine2[1] << ")   -> " << DP[pos][numSituation] << "\n";
		}
	}
	
	cout << DP[0][SituationToInt({{-1,-1},{-1,-1}})] << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8