#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N=100005;
const int INF=1000000000;
int n;
char a[N];
int dp[4][4][4][4];
int ydp[4][4][4][4];
int main()
{
//freopen("input.txt","r",stdin);
cin>>n;
cin>>a;
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
dp[x1][y1][x2][y2]=-INF;
dp[3][3][3][3]=0;
for(int i=1;i<=n;++i)
{
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
ydp[x1][y1][x2][y2]=-INF;
int z;
if(a[i-1]=='M')
z=0;
else if(a[i-1]=='B')
z=1;
else
z=2;
for(int x1=0;x1<4;++x1)
{
for(int y1=0;y1<4;++y1)
{
for(int x2=0;x2<4;++x2)
{
for(int y2=0;y2<4;++y2)
{
int b[4]={};
b[x1]=1;
b[y1]=1;
b[z]=1;
ydp[y1][z][x2][y2]=max(ydp[y1][z][x2][y2],dp[x1][y1][x2][y2]+b[0]+b[1]+b[2]);
b[0]=0;
b[1]=0;
b[2]=0;
b[x2]=1;
b[y2]=1;
b[z]=1;
ydp[x1][y1][y2][z]=max(ydp[x1][y1][y2][z],dp[x1][y1][x2][y2]+b[0]+b[1]+b[2]);
}
}
}
}
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
dp[x1][y1][x2][y2]=ydp[x1][y1][x2][y2];
}
int ans=-INF;
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
ans=max(ans,dp[x1][y1][x2][y2]);
cout<<ans<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
159 ms |
632 KB |
Output is correct |