#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 100001,INF=1e12;
int n;
string s;
int dp[N][4][4][4][4];
int check(int a,int b,int c){
set<int>st;
if(a!=0) st.insert(a);
if(b!=0) st.insert(b);
if(c!=0) st.insert(c);
return st.size();
}
int solve(int i,int preva1,int prevb1,int preva2,int prevb2)
{
//cout<<i<<" "<<preva1<<" "<<preva2<<" "<<prevb1<<" "<<prevb2<<endl;
if(i==n) return 0;
int ans=0;
if(dp[i][preva1][prevb1][preva2][prevb2]!=-1) return dp[i][preva1][prevb1][preva2][prevb2];
int x; if(s[i]=='M') x=1; else if(s[i]=='B') x=2; else x=3;
ans=solve(i+1,preva1,prevb1,prevb2,x)+check(preva2,prevb2,x);
ans=max(ans,solve(i+1,prevb1,x,preva2,prevb2)+check(preva1,prevb1,x));
return dp[i][preva1][prevb1][preva2][prevb2]=ans;
}
int32_t main()
{
//freopen("abc.in", "r", stdin);
cin >> n ;
cin>>s;
memset(dp,-1,sizeof dp);
cout<<solve(0,0,0,0,0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
200584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
200568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
200616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
200652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
200652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
200612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
200660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
201052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
201656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
203084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
392 ms |
207844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
839 ms |
210280 KB |
Output is correct |