#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
const int INF = 1<<30;
string str;
int dp[1+MAX_N][4][4][4][4];
int conv(char x) {
if(x == 'M')
return 1;
if(x == 'B')
return 2;
return 3;
}
int cost(int a, int b, int c) {
if(a == 0 && b == 0)
return 1;
if(a == 0)
return 1 + (b != c);
if(a == b && b == c)
return 1;
else if(a != b && a != c && b != c)
return 3;
return 2;
}
int main() {
int n;
cin >> n >> str;
for(int i = 0; i <= n; ++i)
for(int a1 = 0; a1 < 4; ++a1)
for(int b1 = 0; b1 < 4; ++b1)
for(int a2 = 0; a2 < 4; ++a2)
for(int b2 = 0; b2 < 4; ++b2)
dp[i][a1][b1][a2][b2] = -INF;
dp[0][0][0][0][0] = 0;
for(int i = 0; i < n; ++i) {
int c = conv(str[i]);
for(int a1 = 0; a1 < 4; ++a1)
for(int b1 = 0; b1 < 4; ++b1)
for(int a2 = 0; a2 < 4; ++a2)
for(int b2 = 0; b2 < 4; ++b2) {
dp[i + 1][a1][b1][b2][c] = max(dp[i + 1][a1][b1][b2][c],
dp[i][a1][b1][a2][b2] + cost(a2, b2, c));
dp[i + 1][b1][c][a2][b2] = max(dp[i + 1][b1][c][a2][b2],
dp[i][a1][b1][a2][b2] + cost(a1, b1, c));
}
}
int rez = -INF;
for(int a1 = 0; a1 < 4; ++a1)
for(int b1 = 0; b1 < 4; ++b1)
for(int a2 = 0; a2 < 4; ++a2)
for(int b2 = 0; b2 < 4; ++b2)
rez = max(rez, dp[n][a1][b1][a2][b2]);
cout << rez;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
5368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
10360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
25516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
75768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
199 ms |
100872 KB |
Output is correct |