제출 #618826

#제출 시각아이디문제언어결과실행 시간메모리
6188261neMiners (IOI07_miners)C++14
100 / 100
231 ms116452 KiB
#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	string s;cin>>s;
	auto getid = [&](char u){
		if (u == 'M')return 1;
		else if (u == 'B')return 2;
		return 3;
	};
	int dp[n][4][4][4][4];
	for (int i = 0;i<n;++i){
		for (int j = 0;j<4;++j){
			for (int k = 0;k<4;++k){
				for (int l = 0;l<4;++l){
					for (int m = 0;m<4;++m){
						dp[i][j][k][l][m] = -1;
					}
				}
			}
		}
	}
	function<int(int,int,int,int,int)>solve = [&](int u,int prev,int prev2,int prev3,int prev4){
		if (u == n)return 0;
		if (dp[u][prev][prev2][prev3][prev4]!=-1)return dp[u][prev][prev2][prev3][prev4];
		int temp = getid(s[u]);
		int cnts = 0,cnts2 = 0;
		if (prev != 0)cnts++;
		if (prev2 != 0 && prev2!=prev)cnts++;
		if (temp!=prev && temp!=prev2)cnts++;
		if (prev3 != 0)cnts2++;
		if (prev4 != 0 && prev4!=prev3)cnts2++;
		if (temp!=prev3 && temp!=prev4)cnts2++;
		long long ans = max(solve(u + 1,prev2,temp,prev3,prev4) + cnts , solve(u + 1,prev,prev2,prev4,temp) + cnts2);
		return dp[u][prev][prev2][prev3][prev4] = ans; 
	};
	cout<<solve(0,0,0,0,0)<<'\n';
	return 0;
}
#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...