제출 #237463

#제출 시각아이디문제언어결과실행 시간메모리
237463nikatamlianiMiners (IOI07_miners)C++14
100 / 100
108 ms628 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int dp[2][4][4][4][4], ans = 0;
string s;
int diff(int t1, int t2, int t3){
	bool f[4] = {0, 0, 0, 0}; 
	f[t1] = f[t2] = f[t3] = 1;
	return f[1] + f[2] + f[3]; 
}
int main(){
	memset(dp, -1, sizeof dp);
	dp[0][0][0][0][0] = 0;
	int n;
	string s;
	cin >> n >> s;
	s = "@" + s;
	for(int i = 1; i <= n; ++i){
		int t = 1;
		if(s[i] == 'B')t = 2;
		if(s[i] == 'F')t = 3;
		for(int t0 = 0; t0 < 4; ++t0){
			for(int t1 = 0; t1 < 4; ++t1){
				for(int T0 = 0; T0 < 4; ++T0){
					for(int T1 = 0; T1 < 4; ++T1){
						int &dp0 = dp[1][t1][t][T0][T1];
						int &dp1 = dp[1][t0][t1][T1][t];
						int opt = dp[0][t0][t1][T0][T1];
						if(~opt){
							dp0 = max(dp0, opt + diff(t0, t1, t));
							dp1 = max(dp1, opt + diff(T0, T1, t));
						}
					}
				}
			}
		}
		for(int t0 = 0; t0 < 4; ++t0){
			for(int t1 = 0; t1 < 4; ++t1){
				for(int T0 = 0; T0 < 4; ++T0){
					for(int T1 = 0; T1 < 4; ++T1){
						dp[0][t0][t1][T0][T1] = dp[1][t0][t1][T0][T1];
						dp[1][t0][t1][T0][T1] = -1;
					}
				}
			}
		}
	}
	for(int t0 = 0; t0 < 4; ++t0){
		for(int t1 = 0; t1 < 4; ++t1){
			for(int T0 = 0; T0 < 4; ++T0){
				for(int T1 = 0; T1 < 4; ++T1){
					ans = max(ans, dp[0][t0][t1][T0][T1]);
				}
			}
		}
	}
	cout << ans << endl;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...